Коды Лемпеля-Зива

Основной сложностью при использовании кода Хаффмана является то, что вероятности символов должны быть известны и оценены и как кодер, так и декодер должны знать дерево кодирования. Если дерево строится для необычного для кодера алфавита, канал, связывающий с кодером и декодером, должен также отправлять кодовирующее дерево как заголовок сжатого файла. Эти служебные издержки снижают эффективность сжатия, реализуемого с помощью построения и применения дерева к алфавиту источника. Алгоритм Лемпеля-Зива и его многочисленные разновидности используют текст сам по себе для построения синтаксически выделенной последовательности кодовых слов переменной длины, которые образуют кодовый словарь.

Код предполагает, что существующие слова содержат уже закодированные сегменты последовательности символов алфавита. Данные кодируются с помощью просмотра существующего словаря для согласования со следующим коротким сегментом кодируемой последовательности. Если согласование найдено, код следует такой концепции: поскольку получатель уже имеет этот сегмент кода в своей памяти, нет необходимости пересылать его, требуется только определить адрес, чтобы найти сегмент. Код ссылается на расположение последовательности сегмента и затем дополняет следующий символ в последовательности, чтобы образовать новую позицию в словаре кода. Код начинается с пустого словаря, так что первыми элементами являются позиции, которые не ссылаются на более ранние. В одной форме словаря рекуррентно (последовательно) формируется выполняемая последовательность адресов и сегмент символов алфавита, содержащийся в ней. Закодированные данные состоят из пакета («адрес словаря, следующий знак данных»), а каждый новый входной сегмент словаря образован как пакет, содержащий адрес того словаря, за которым следует следующий символ.

Рассмотрим пример такой технологии кодирования:

Закодируем последовательность символов:

[abaababbbbbbbabbbbba]

Закодированные пакеты:

<0, a> <0,b> <1,a> <2,а> <2,b> <5, b> <5,a> <6,b> <4,–>

Адрес: 1 2 3 4 5 6 7 8

Содержимое: a b aa ba bb bbb bba bbbb

Начальный пакет <0, a> показывает нулевой адрес, потому что в словаре ещё нет ни одной позиции. В этом пакете знак <а> является первым в последовательности данных, и он приписан к адресу 1. Следующий пакет <0,b> содержит второй знак данных <b>, который ещё не был в словаре (поэтому адресное значение есть 0); b приписывается адресу 2. Пакет <1,a> представляет кодирование следующих двух знаков <аа> с помощью вызова адреса 1 для первого и присоединения к этому адресу следующего знака «а». Пара <aa> приписывается адресу 3. Пакет <2,а> представляет собой кодирование следующих двух знаков «ba» с помощью вызова адреса 2 для знака «b» и присоединение к этому адресу следующего знака «а». Пара знаков данных «ba» приписывается адресу 4 и т.д. Восьмой пакет предполагает вызов адреса 6, содержащего три знака «bbb», за которыми следует другой знак «b».

В этом примере закодированные данные могут быть описаны с помощью трехбитового адреса с последующим битом 0 и 1 для определения присоединённого знака. Закодированная последовательность содержит 9 пакетов, содержащих по 4 двоичных знака, т.е. включает всего 36 двоичных знака. При этом, исходная последовательность содержала лишь 20 двоичных знаков, следовательно, алгоритм не обеспечил сжатие данных. Однако неэффективность является следствием того, что кодируемая последовательность очень коротка. По мере увеличения длины последовательности процедура кодирования становится более эффективной и приводит к сжатию последовательности на выходе источника.

При реализации данного алгоритма независимо от объёма памяти, используемого для создания словаря, он в конечном счете переполняется. Чтобы решить проблему переполнения, кодер и декодер должны удалять из словарей сегменты, которые долго не используются и заполнять их новым содержимым. Алгоритм Лемпеля-Зива эффективно используются при сжатии файлов.