11

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

舉例來說,我想:ABCBCABCBCDEEF成爲:(2A(2BC))d(2E)的F

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

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

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

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

歡迎的想法。

+0

你能否澄清Huffman或Golomb編碼是否足夠? – Iterator

+0

'ABABABAB'是'4(AB)'還是'2(2(AB))'?或'2(ABAB)'? –

+0

這些模式有多長? –

回答

3

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

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

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

正如你所看到的,編碼ABBA(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; 
     } 
    } 
} 
+0

@ lasse-v-karlsen哇 - 比我的測試案例更快,更準確...整潔。將花費我一段時間來消化和編輯,但肯定會在看這個解決方案。非常感謝 – user858203

+0

看到更長,更大的例子將是非常有趣的。當我今晚晚些時候回到我的電腦時,我會看看「第一個2+重複」,看看我能否做得更好。 –

+0

不是一個網絡人我把代碼和翻譯到Java,但它是類似於你的。如果我在週末有時間,我也會考慮你的潛在增強。我還提出了一些其他的測試案例,由朋友提供,並應用了你的算法:ABCBCABCBCDEEF =(2A(2BC))D(2E)F ok對我來說看起來不錯。 (3A(2B))ABA好的,還有其他的選擇,但我認爲不是更簡潔。 ABCDABCDCDCDCD =(2ABCD)(3CD)再次有選擇,但我認爲不是更簡潔。 (2AB)ABABCDABCD =(2AB)CDABCD--不正確的應該是AB(2ABCD) – user858203

1

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

 

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

ABABCDABABCD 
s->ABtt 
t->ABCD 

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

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