Сжатие информации с учетом цепочек символов по Лемпелю-Зиву.

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

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

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

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

Уточним дополнительно некоторые моменты:

коды координат цепочки и коды отдельных символов различаются битовыми признаками (например, в первом случае – 1, во втором –0) ;

поскольку цепочки находятся чаще в начале словаря, и чаще бывают короткими, дополнительный выигрыш получают за счет статистического кодирования (по Хаффмену) их «адресов» и «длин»;

«канал» - понятие применимое и к реальному каналу передачи данных, и к файлу, куда данные записываются для хранения. В последнем случае декодер «отрабатывает» при разворачивании сжатого файла;

при ограниченной длине словаря (обычно от 4 до 16 кбайт) новые поступающие символы и цепочки «вытесняют» прежние (текст как бы «вдвигается» в словарь). Разумеется, вначале, когда словарь не заполнен, эффективность сжатия невысока. Рост объема словаря позволяет повысить степень сжатия, но значительно увеличивается трудоемкость поиска цепочек.

Добавим, что алгоритм Лемпеля-Зива используется в большинстве популярных программ-архиваторов (в том числе, например, в zip, rar, arj и их windows – версиях).

Различие скорости и эффективности кодирование-декодирование определяются в основном особенностями программной реализации.

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