11

我想总结而不是以与运行长度编码类似的方式进行压缩，但在嵌套的意义上。

例如，我希望： ABCBCABCBCDEEF 变为： (2A(2BC))D(2E)F

我不担心在两个相同的可能嵌套之间选择一个选项，例如

ABBABBABBABA 可以是 (3ABB)ABA 或 A(3BBA)BA，它们具有相同的压缩长度，尽管具有不同的结构。

但是我确实希望选择是最贪婪的。例如：

ABCDABCDCDCD 将选择 (2ABCD)(3CD) - 原始符号中长度为 6 的长度小于原始符号中长度为 8 的 ABCDAB(4CD)。

在背景方面，我想总结一些重复的模式。让数据更易消化。我不想破坏数据的逻辑顺序，因为它很重要。但我确实想总结一下，比如符号 A 出现 3 次，然后是符号 XYZ 出现 20 次等等，这可以在视觉上以嵌套的方式显示。

欢迎提出想法。

4

2 回答 2

3

我很确定这不是最好的方法，并且根据模式的长度，运行时间和内存使用可能不起作用，但这里有一些代码。

您可以将以下代码粘贴到LINQPad中并运行它，它应该会产生以下输出：

ABCBCABCBCDEEF = (2A(2BC))D(2E)F
ABBABBABBABA = (3A(2B))ABA
ABCDABCDCDCD = (2ABCD)(3CD)

如您所见，中间示例编码ABB为A(2B)而不是ABB，您必须自己做出判断，是否应该将这样的单符号序列编码为重复符号，或者是否有特定阈值（如 3 或更多）应该使用。

基本上，代码运行如下：

  1. 对于序列中的每个位置，尝试找到最长的匹配（实际上，它没有，它需要找到的第一个 2+ 匹配，我把剩下的留给你作为练习，因为我必须离开我的电脑几现在几个小时）
  2. 然后它尝试对该序列进行编码，该序列以递归方式重复并吐出 X*seq 类型的对象
  3. 如果找不到重复序列，则在该位置吐出单个符号
  4. 然后它会跳过它编码的内容，并从 #1 继续

无论如何，这是代码：

void Main()
{
    string[] examples = new[]
    {
        "ABCBCABCBCDEEF",
        "ABBABBABBABA",
        "ABCDABCDCDCDCD",
    };

    foreach (string example in examples)
    {
        StringBuilder sb = new StringBuilder();
        foreach (var r in Encode(example))
            sb.Append(r.ToString());
        Debug.WriteLine(example + " = " + sb.ToString());
    }
}

public static IEnumerable<Repeat<T>> Encode<T>(IEnumerable<T> values)
{
    return Encode<T>(values, EqualityComparer<T>.Default);
}

public static IEnumerable<Repeat<T>> Encode<T>(IEnumerable<T> values, IEqualityComparer<T> comparer)
{
    List<T> sequence = new List<T>(values);

    int index = 0;
    while (index < sequence.Count)
    {
        var bestSequence = FindBestSequence<T>(sequence, index, comparer);
        if (bestSequence == null || bestSequence.Length < 1)
            throw new InvalidOperationException("Unable to find sequence at position " + index);

        yield return bestSequence;
        index += bestSequence.Length;
    }
}

private static Repeat<T> FindBestSequence<T>(IList<T> sequence, int startIndex, IEqualityComparer<T> comparer)
{
    int sequenceLength = 1;
    while (startIndex + sequenceLength * 2 <= sequence.Count)
    {
        if (comparer.Equals(sequence[startIndex], sequence[startIndex + sequenceLength]))
        {
            bool atLeast2Repeats = true;
            for (int index = 0; index < sequenceLength; index++)
            {
                if (!comparer.Equals(sequence[startIndex + index], sequence[startIndex + sequenceLength + index]))
                {
                    atLeast2Repeats = false;
                    break;
                }
            }
            if (atLeast2Repeats)
            {
                int count = 2;
                while (startIndex + sequenceLength * (count + 1) <= sequence.Count)
                {
                    bool anotherRepeat = true;
                    for (int index = 0; index < sequenceLength; index++)
                    {
                        if (!comparer.Equals(sequence[startIndex + index], sequence[startIndex + sequenceLength * count + index]))
                        {
                            anotherRepeat = false;
                            break;
                        }
                    }
                    if (anotherRepeat)
                        count++;
                    else
                        break;
                }

                List<T> oneSequence = Enumerable.Range(0, sequenceLength).Select(i => sequence[startIndex + i]).ToList();
                var repeatedSequence = Encode<T>(oneSequence, comparer).ToArray();
                return new SequenceRepeat<T>(count, repeatedSequence);
            }
        }

        sequenceLength++;
    }

    // fall back, we could not find anything that repeated at all
    return new SingleSymbol<T>(sequence[startIndex]);
}

public abstract class Repeat<T>
{
    public int Count { get; private set; }

    protected Repeat(int count)
    {
        Count = count;
    }

    public abstract int Length
    {
        get;
    }
}

public class SingleSymbol<T> : Repeat<T>
{
    public T Value { get; private set; }

    public SingleSymbol(T value)
        : base(1)
    {
        Value = value;
    }

    public override string ToString()
    {
        return string.Format("{0}", Value);
    }

    public override int Length
    {
        get
        {
            return Count;
        }
    }
}

public class SequenceRepeat<T> : Repeat<T>
{
    public Repeat<T>[] Values { get; private set; }

    public SequenceRepeat(int count, Repeat<T>[] values)
        : base(count)
    {
        Values = values;
    }

    public override string ToString()
    {
        return string.Format("({0}{1})", Count, string.Join("", Values.Select(v => v.ToString())));
    }

    public override int Length
    {
        get
        {
            int oneLength = 0;
            foreach (var value in Values)
                oneLength += value.Length;
            return Count * oneLength;
        }
    }
}

public class GroupRepeat<T> : Repeat<T>
{
    public Repeat<T> Group { get; private set; }

    public GroupRepeat(int count, Repeat<T> group)
        : base(count)
    {
        Group = group;
    }

    public override string ToString()
    {
        return string.Format("({0}{1})", Count, Group);
    }

    public override int Length
    {
        get
        {
            return Count * Group.Length;
        }
    }
}
于 2011-07-29T14:40:43.643 回答
1

从理论上看这个问题，它似乎类似于找到生成（仅）字符串的最小上下文无关语法的问题，除了在这种情况下，非终结符只能在彼此之后直接使用，所以例如

ABCABCABCDEEF
s->ttDuF
t->Avv
v->BC
u->E

ABABCDABACD
s->ABtt
t->ABCD

当然，这取决于您如何定义“最小”，但是如果您计算规则右侧的终端，则它应该与进行嵌套游程编码后的“原始符号长度”相同。

最小语法问题是众所周知的难题，并且是一个经过充分研究的问题。我不知道“直接序列”部分增加或减少了多少复杂性。

于 2011-07-31T02:15:39.237 回答