我想總結而不是以類似的方式壓縮運行長度編碼，但在嵌套的意義上。無損層次運行長度編碼
舉例來說，我想：ABCBCABCBCDEEF成爲：（2A（2BC））d（2E）的F
我並不擔心，一個選項是兩個相同的可能嵌套捏起例如儘管具有不同的結構，ABBABBABBABA可以是（3ABB）ABA或A（3BBA）BA，其具有相同的壓縮長度。
但是我確實希望選擇是最貪婪的。例如：
ABCDABCDCDCDCD會選取原始符號長度爲6的小於ABCDAB（4CD）的原始符號長度爲8的長度爲6的（2ABCD）（3CD）。
在背景方面我有一些我想總結的重複模式。這樣的數據更容易消化。我不想破壞數據的邏輯順序，因爲它很重要。但我想總結它，通過說，符號A次3次出現，其次是符號XYZ出現20次等，並且這可以以視覺上嵌套的方式顯示。
歡迎的想法。
我敢肯定，這不是最好的方法，根據模式的長度，可能會有運行時間和內存使用情況不起作用，但這裏有一些代碼。
您可以將下面的代碼粘貼到LINQPad並運行它，它應該會產生以下的輸出：
ABCBCABCBCDEEF = (2A(2BC))D(2E)F ABBABBABBABA = (3A(2B))ABA ABCDABCDCDCDCD = (2ABCD)(3CD)
正如你所看到的，編碼ABB爲A(2B)，而不是ABB中間的例子中，你將有如果像這樣的單符號序列應該被編碼爲重複符號，或者如果應該使用特定的閾值（如3或更多），那麼您自己做出判斷。
基本上，代碼運行是這樣的：
反正下去，下面的代碼：
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;
}
}
}
@ lasse-v-karlsen哇 - 比我的測試案例更快，更準確...整潔。將花費我一段時間來消化和編輯，但肯定會在看這個解決方案。非常感謝 – user858203
看到更長，更大的例子將是非常有趣的。當我今晚晚些時候回到我的電腦時，我會看看「第一個2+重複」，看看我能否做得更好。 –
不是一個網絡人我把代碼和翻譯到Java，但它是類似於你的。如果我在週末有時間，我也會考慮你的潛在增強。我還提出了一些其他的測試案例，由朋友提供，並應用了你的算法：ABCBCABCBCDEEF =（2A（2BC））D（2E）F ok對我來說看起來不錯。 （3A（2B））ABA好的，還有其他的選擇，但我認爲不是更簡潔。 ABCDABCDCDCDCD =（2ABCD）（3CD）再次有選擇，但我認爲不是更簡潔。 （2AB）ABABCDABCD =（2AB）CDABCD--不正確的應該是AB（2ABCD） – user858203
望着理論上的問題，似乎類似於尋找最小的範圍內自由的問題只產生字符串的語法，除非在這種情況下，非終端只能在彼此之後直接使用，例如
ABCBCABCBCDEEF s->ttDuuF t->Avv v->BC u->E ABABCDABABCD s->ABtt t->ABCD
當然，這取決於你如何定義「最小的」，但如果你指望規則的右側終端，它應該做的巢式運行後是一樣的「在原來的符號長度」長度編碼。
語法最小的問題已知很難，而且是一個研究得很好的問題。我不知道「直接序列」部分增加或減少複雜性的程度。
你能否澄清Huffman或Golomb編碼是否足夠？ – Iterator
'ABABABAB'是'4（AB）'還是'2（2（AB））'？或'2（ABAB）'？ –
這些模式有多長？ –