11

ランレングスエンコーディングと同様の方法で圧縮するのではなく、ネストされた意味で要約したいと思います。

たとえば、次のようになりたい: ABCBCABCBCDEEF : (2A(2BC))D(2E)F

オプションが2つの同一の可能な入れ子の間で選択されることは気にしませんEg

ABBABBABBABA は (3ABB)ABA または A(3BBA)BA であり、構造は異なりますが、圧縮された長さは同じです。

しかし、私はその選択が最も貪欲であることを望んでいます。例えば：

ABCDABCDCDCDCD は (2ABCD)(3CD) を選択します - 元のシンボルの長さは 6 で、元のシンボルの長さは 8 である ABCDAB(4CD) よりも小さいです。

背景に関しては、要約したい繰り返しのパターンがいくつかあります。データがより消化しやすいように。重要であるため、データの論理的な順序を乱したくありません。しかし、私はそれを要約したいと思います。シンボル A に 3 回出現し、その後にシンボル XYZ が 20 回出現するなど、これはネストされた意味で視覚的に表示できます。

アイデアを歓迎します。

4

2 に答える 2

3

これが最善のアプローチではないことは確かです。パターンの長さによっては、実行時間とメモリ使用量がうまくいかない可能性がありますが、ここにいくつかのコードを示します。

次のコードをLINQPadに貼り付けて実行すると、次の出力が生成されます。

ABCBCABCBCDEEF = (2A(2BC))D(2E)F
アババババ = (3A(2B))アバ
ABCDABCDCDCDCD = (2ABCD)(3CD)

ご覧のように、代わりにとしてエンコードさABBれた中央の例では、そのような単一シンボル シーケンスを繰り返しシンボルとしてエンコードする必要があるかどうか、または特定のしきい値 (3 以上など) であるかどうかを自分で判断する必要があります。使用すべきです。A(2B)ABB

基本的に、コードは次のように実行されます。

  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

この問題を理論的に見ると、文字列を (のみ) 生成する最小の文脈自由文法を見つける問題に似ているように見えますが、この場合、非終端記号は互いに直接の順序でしか使用できないため、たとえば

ABCBCABCBCDEEF
s->ttDuuF
t->平均
v->紀元前
u->E

あああああああああ
s->ABtt
t->ABCD

もちろん「最小」の定義にもよりますが、規則の右辺で端子を数えると、入れ子ランレングス符号化を行った後の「元のシンボルでの長さ」と同じになるはずです。

最小文法の問題は難しいことが知られており、よく研究されている問題です。「直接シーケンス」部分が複雑さをどれだけ増減するかはわかりません。

于 2011-07-31T02:15:39.237 に答える