Словарные и словарно-статистические алгоритмы сжатия

В 1977 г. израильские ученые А. Лемпсл и Я. Зив предложили алгоритм сжатия данных, названный позже LZ. На основе этого алгоритма в дальнейшем было разработано множество алгоритмов, учитывающих технические возможности компьютеров. В алгоритмах LZ учитываются корреляционные связи между символами, что позволяет значительно увеличить коэффициент сжатия.

Сущность алгоритма сжатия данных LZ состоит в том, что повторяющиеся последовательности символов заменяются указателями на позиции, где они в тексте уже ранее появлялись. Одной из форм такого указателя может быть пара («, т), которая ссылается на последовательность символов длиной т, начинающуюся с позиции п. В большинстве реализаций алгоритма Лепеля — Зива позиция в парс кодируется как смещение (разность) между позициями кодируемой строки и строки, на которую произведена ссылка.

Из-за ограниченного объема оперативной памяти компьютера обычно используется вариант алгоритма Лсмпсля — Зива со скользящим окном, когда максимальное значение смещения ограничено некоторым значением.

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