可逆階層ランレングス符号化

Question

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

は、例えば、私がしたい：ABCBCABCBCDEEFになる：（2A（2BC））D（2E）F

Iオプションは、例えば、二つの同一の可能なネスティングの間に捕捉されることはない心配します

ABBABBABBABAは、異なる構造を有するにもかかわらず、同じ圧縮長さの（3ABB）ABAまたはA（3BBA）BAであり得る。

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

ABCDABCDCDCDCDは元のシンボルの長さ8であるABCDAB（4CD）未満の元のシンボルでは長さ6のピックアップ（2ABCD）（3CD）です。

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

ようこそ。

Answer 1

これは最善のアプローチではないと確信していますが、パターンの長さによっては動作しないメモリ使用量があるかもしれませんが、ここにいくつかのコードがあります。

あなたはLINQPadに次のコードを貼り付け、それを実行し、それは以下のような出力を生成する必要がありすることができます

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

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

基本的には、コードは次のように実行します：シーケンス内の各位置について

1. 、最長一致（実際に、それは、それが最初になりますしません2+、見つかった一致を見つけようと、I
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; 
     } 
    } 
} 

Answer 2

は、それが最小の文脈自由を見つける問題に似ているようです文字列を生成する文法（この場合を除いて）は、非終端記号は直接の順序でしか使用できません。もちろん

 

ABCBCABCBCDEEF 
s->ttDuuF 
t->Avv 
v->BC 
u->E 

ABABCDABABCD 
s->ABtt 
t->ABCD 

が、これは、あなたが「最小」をどう定義するかに依存しますが、あなたは、ルールの右側にある端末をカウントした場合、それは、ネストされた実行をした後、「オリジナルのシンボルの長さ」と同じでなければなりません-lengthエンコード

最小の文法の問題は困難であることが知られており、よく研究されている問題です。私は、「直接的なシーケンス」の部分が複雑さに加わるか、それとも減じるかは分かりません。