Алгоритм Лемпела-Зива

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

Словом в этом алгоритме называется последовательность символов (не обязательно совпадающая со словом естественного языка). Слова хранятся в словаре, а их вхождения в исходные данные заменяются адресами (номерами) слов в словаре. Некоторые разновидности алгоритма хранят отдельно словарь и отдельно упакованные данные в виде последовательности номеров слов. Другие считают словарем весь уже накопленный результат сжатия. Например, сжатый файл может состоять из записей вида [a,l,t], где a – адрес (номер позиции), с которой начинается такая же строка длины l, что и текущая строка. Если a>0, то запись считается ссылкой на словарь и поле t (текст) в ней – пустое. Если a = 0, то в поле t записаны l символов, которые до сих пор в такой последовательности не встречались.

Алгоритм сжатия заключается в постоянном поиске в уже упакованной части данных максимальной последовательности символов, совпадающей с последовательностью, начинающейся с текущей позиции. Если такая последовательность (длины > 3) найдена, в результат записывается ее адрес и длина. Иначе в результат записывается 0, длина последовательности и сама (несжатая) последовательность.