無損層次運行長度編碼

Question

我想總結而不是以類似的方式壓縮運行長度編碼，但在嵌套的意義上。

舉例來說，我想：ABCBCABCBCDEEF成爲：（2A（2BC））d（2E）的F

我並不擔心，一個選項是兩個相同的可能嵌套捏起例如儘管具有不同的結構，ABBABBABBABA可以是（3ABB）ABA或A（3BBA）BA，其具有相同的壓縮長度。

但是我確實希望選擇是最貪婪的。例如：

ABCDABCDCDCDCD會選取原始符號長度爲6的小於ABCDAB（4CD）的原始符號長度爲8的長度爲6的（2ABCD）（3CD）。

在背景方面我有一些我想總結的重複模式。這樣的數據更容易消化。我不想破壞數據的邏輯順序，因爲它很重要。但我想總結它，通過說，符號A次3次出現，其次是符號XYZ出現20次等，並且這可以以視覺上嵌套的方式顯示。

歡迎的想法。

Answer 1

我敢肯定，這不是最好的方法，根據模式的長度，可能會有運行時間和內存使用情況不起作用，但這裏有一些代碼。

您可以將下面的代碼粘貼到LINQPad並運行它，它應該會產生以下的輸出：

 
ABCBCABCBCDEEF = (2A(2BC))D(2E)F 
ABBABBABBABA = (3A(2B))ABA 
ABCDABCDCDCDCD = (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; 
     } 
    } 
} 

Answer 2

望着理論上的問題，似乎類似於尋找最小的範圍內自由的問題只產生字符串的語法，除非在這種情況下，非終端只能在彼此之後直接使用，例如

 

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

ABABCDABABCD 
s->ABtt 
t->ABCD 

當然，這取決於你如何定義「最小的」，但如果你指望規則的右側終端，它應該做的巢式運行後是一樣的「在原來的符號長度」長度編碼。

語法最小的問題已知很難，而且是一個研究得很好的問題。我不知道「直接序列」部分增加或減少複雜性的程度。