2.3. LZ78

Метод LZ78 (иногда его называют LZ2, см. [Ziv 78]) не использует буфер поиск, упреждающий буфер и скользящее окно. Вместо этого имеется словарь встретившихся ранее строк. В начале этот словарь пуст (или почти пуст), и размер этого словаря ограничен только объемом доступной памяти. На выход кодера поступает последовательность меток, состоящих из двух полей. Первое поле - это указатель на строку в словаре, а второе код символа. Метка не содержит длины строки, поскольку строка берется из словаря. Каждая метка соответствует последовательности во входном файле, и эта последовательность добавляется в словарь после того, как метка записана в выходной сжатый файл. Ничего из словаря не удаляется, что является одновременно и преимуществом над LZ77 (поскольку будущие строки могут совпадать даже с очень давними последовательностями) и недостатком (так как быстро растет объем словаря).

Словарь начинает строиться из пустой строки в позиции нуль. По мере поступления и кодирования символов, новые строки добавляются в позиции 1, 2 и т.д. Когда следующий символ  читается из входного файла, в словаре ищется строка из одного символа . Если такой строки нет, то  добавляется в словарь, а на выход подается метка . Эта метка означает строку «нуль » (соединение нулевой строки и ). Если вхождение символа  обнаружено (скажем, в позиции 37), то читается следующий символ , и в словаре ищется вхождение двухсимвольной строки . Если такое не найдено, то в словарь записывается строка , а на выход подается метка . Такая метка означает строку , так как позицию 37 в словаре занимает символ . Процесс продолжается до конца входного файла.

В общем случае текущий символ читается и становится однобуквенной строкой. Затем кодер пытается найти ее в словаре. Если строка найдена, читается следующий символ и присоединяется к текущей строке, образуя двухбуквенную строку, которую кодер опять пытается найти в словаре. До тех пор пока такие строки находятся в словаре, происходит чтение новых символов и их присоединение к текущей строке. В некоторый момент такой строки в словаре не оказывается. Тогда кодер добавляет ее в словарь и строит метку, в первом поле которой стоит указатель на последнюю найденную в словаре строку, а во втором поле записан последний символ строки (на котором произошел обрыв успешных поисков). В табл. 2.4 показаны шаги при декодировании последовательности «sir_sid_eastman_easily_teases_sea_sick_seals».

Табл. 2.4. Шаги кодирования LZ78.

На каждом шаге строка, добавленная в словарь, совпадает с кодируемой строкой минус последний символ. В типичном процессе сжатия словарь начинается с коротких строк, но по мере продвижения по кодируемому тексту, все более и более длинные строки добавляются в словарь. Размер словаря может быть фиксированным или определяться размером доступной памяти каждый раз, когда запускается программа сжатия LZ78. Большой словарь позволяет делать глубокий поиск длинных совпадений, но ценой этого служит длина поля указателей (а, значит, и длина метки) и замедление процесса словарного поиска.

Хорошей структурой для организации словаря является дерево, но не двоичное. Дерево начинается нулевой строкой в корне. Все строки, начинающиеся с нулевой строки (строки, для которых указатель в метке равен нулю), добавляются к дереву как потомки корня. В нашем примере таковыми служат следующие строки: s, i, r, _, d, a, m, у, е, с, k. Все они становятся корнями поддеревьев, показанных на рис. 2.5. Например, все строки, начинающиеся с символа s (четыре строки si, sil, st и s(eof)) образуют поддерево узла s.

В 8-битовом алфавите имеется всего 256 различных символов. В принципе, каждый узел дерева может иметь до 256 потомков. Следовательно, добавление новых узлов на дерево является динамическим процессом. Когда узел будет создаваться, у него еще нет потомков, поэтому необходимо зарезервировать некоторый объем памяти для них. Поскольку удалять узлы с дерева не придется, не придется и заниматься перераспределением памяти, что несколько упрощает манипулирование с ней.

Рис. 2.5. Словарное дерево для LZ78.

На таком дереве очень легко искать строки и добавлять новые символы. Например, чтобы найти строку sil, программа ищет символ s в корне, затем его потомка i символа s, и так далее, спускаясь вниз по дереву. Вот еще некоторые примеры.

1. Когда символ s из sid появляется на входе при шаге 5, кодер находит узел «1-s» на дереве как потомка «null». Затем поступает символ i, но узел s не имеет такого потомка (у него в этот момент вовсе нет потомков). Тогда кодер добавляет узел «5-i» в виде потомка узла «1-s», что означает добавление на дерево строки si.

2. Когда на входе появляется пробел между eastman и easily на шаге 12, возникает похожая ситуация. Кодер обнаруживает узел «4-_», получает символ е, находит «7-е», получает а, но у «7-е» нет потомка а, поэтому он добавляет узел «12-а», что эквивалентно добавлению строки «_еа».

Возникающие деревья относятся к специальному типу деревьев, в которых образование новых веток и их дальнейшее ветвление зависит только от части поступающих новых данных, а не от всех данных. В случае LZ78, новая ветвь соответствует всего одному новому добавляемому символу.

Поскольку размер дерева ничем не ограничен, может возникнуть переполнение. На самом деле, это всегда происходит, за исключением тех случаев, когда входной файл имеет малый размер. Первоначальный LZ78 метод не устанавливает, что делать в этом случае. Он является, скорее, теоретическим методом, который удобно исследовать, но трудно использовать на практике. Ниже приводятся некоторые возможные решения этой проблемы.

1. Простейшее решение это заморозить словарь, когда он переполнится. Новые узлы не добавляются, словарь становится статическим, но с его помощью можно по-прежнему кодировать последовательности.

2. Удалить все дерево при переполнении и начать строить новое. Это решение эффективно разбивает данные на блоки, и в каждом блоке используется свой собственный словарь. Если содержимое сжимаемых данных меняется от блока к блоку, то этот метод дает хорошие результаты, поскольку в словаре не хранятся строки, которые с малой вероятностью поступят в дальнейшем. Здесь опять, как и в LZ77 неявно предполагается, что похожие данные будут группироваться близко друг к другу.

3. Утилита compress операционной системы UNIX использует более сложное решение. Эта программа (еще называемая LZC) использует алгоритм LZW (см. § 2.4) с растущим словарем. Она начинает работать с маленьким словарем, состоящим всего из  строк, причем первые 256 уже заполнены. При использовании исходного словаря в сжатый файл записываются 9-битовые указатели. После заполнения этого словаря его размер удваивается до 1024 строк. С этого момента используются 10-битовые указатели. Этот процесс продолжается до тех пор, пока размер указателей не достигнет некоторого максимального значения, задаваемого пользователем (от 9 до 16 бит, причем 16 принято по умолчанию). Когда наибольший допустимый словарь полностью заполняется, программа продолжает работать без изменения словаря (который теперь становится статическим), но одновременно делается мониторинг коэффициента сжатия. Если этот коэффициент превышает некоторый предустановленный порог, то происходит сброс словаря, процесс начинается с исходного 512-строчного словаря. При таком подходе словарь никогда не устаревает.

4. Когда словарь заполнился, удалить из него некоторые самые старые строки, чтобы освободить место для новых. К сожалению, не существует хорошего алгоритма, который определял бы, какие строки удалять и в каком количестве.

Декодер LZ78 работает примерно так же, как и кодер, строя словарь и оперируя с ним. Поэтому он более сложен, чем декодер LZ77.

Эти слова! Как невинно и беспомощно они выглядят в проявляют в руках тех, кто умеет объединять их.
- Натаниэль Хаусорн