Результат сжатия: 0c0a0b2b4a3a5b0m
Словарь хранится в префиксном дереве, что позволяет легко находить самое длинное продолжение входной строки, уже присутствующее в словаре. При декодированиистроитсявточностиэтотжесловарь.Всжатомпредставлении строки словарь не хранится. В начале работы в словаресодержится
единственныйэлементподномеромноль:T0=ε;инымисловами,префиксное дерево состоит из корня, помеченного номером 0. На каждом шаге читается самая длинная строка Tj = v, уже имеющаяся в словаре, и выводится её код j; также читается и выводится следующий символ a. При этом в словарь добавляется новая строка va — конкатенация только что прочитанной со следующим входным символом. На префиксном дереве это выглядит так: послевыводаочереднойпары(j,a)алгоритмпереходитвкореньпрефиксного дерева, и дальше читает столько входных символов, сколько возможно.Когда очередной символ прочитать нельзя, создаётся новый лист, при этом выводится номер предыдущей вершины и прочитанный символ. Пример 2. Строка w = ababaaabb, в таблице T0 =ε.
Кодирование: Читается a, выводится 0a, добавляется T1 = a. Читается b, выводится 0b, добавляется T2 = b.
Читается ab, выводится 1b, добавляется T3 = ab. Читается aa, выводится 1a, добавляется T4 = aa. Читается abb, выводится 3b, добавляется T5 = abb. Код — 0a0b1b1a3b.