6. Алгоритмы Лемпеля – Зива

Это наиболее часто используемые в настоящее время алгоритмы сжатия. Они используются в большинстве программ - архиваторов (например, PKZIP. ARJ, LHA ). Сущность алгоритмов состоит в том, что некоторая совокупность символов заменяется при архивировании её номером в специально формируемом словаре. Например, часто встречающаяся в деловой переписке фраза "На ваше письмо исходящий номер..." может занимать в словаре позицию 121; тогда вместо передачи или хранения упомянутой фразы (30 байт) можно хранить номер фразы (1,5 байта в двоично - десятичной форме или 1 байт - в двоичной).

Алгоритмы названы в честь авторов, впервые предложивших их в 1977 году. Из них первый - LZ77. Для архивирования создается так называемое скользящее по сообщению окно, состоящее из двух частей. Первая часть, большего формата, служит для формирования словаря и имеет размер порядка нескольких килобайт. Во вторую, меньшую часть (обычно размером до 100 байт ) принимаются текущие символы просматриваемого текста. Алгоритм пытается найти в словаре совокупность символов, совпадающую с принятыми в окно просмотра. Если это удаётся, формируется код, состоящий из трёх частей: смещение в словаре относительно его начальной подстроки, длина этой подстроки, следующий за этой подстрокой символ. Например, выделенная подстрока состоит из символов " прилож " (всего 6 символов), следующий за ней символ - "е". Тогда, если подстрока имеет адрес (место в словаре ) 45, то запись в словарь имеет вид "45, 6. е ". После этого содержимое окна сдвигается на позицию, и поиск продолжается. Таким образом формируется словарь.

Достоинством алгоритма является легко формализуемый алгоритм составления словаря. Кроме того, возможно разархивирование и без первоначального словаря ( желательно при этом иметь тестовую последовательность) - словарь формируется по ходу разархивирования.

Недостатки алгоритма появляются при увеличении размера словаря - увеличивается время на поиск. Кроме того, если в текущем окне появляется строка символов, отсутствующая в словаре, трёхэлементным кодом записывается каждый символ, т.е. получается не сжатие, а растяжение.

Лучшие характеристики имеет алгоритм LZSS, предложенный в 1978г. В нём есть отличия в поддержании скользящего окна и выходных кодах компрессора [47]. Помимо окна, алгоритм формирует двоичное дерево, аналогичное дереву Хафмана для ускорения поиска совпадений: каждая подстрока, покидающая текущее окно, добавляется в дерево в качестве одного из детей. Такой алгоритм позволяет дополнительно увеличить размер текущего окна (желательно, чтобы его величина равнялась степени двойки: 128, 256 и т.д. байт ). По - другому формируются и коды последовательностей: дополнительно вводится 1- битный префикс для различения незакодированных символов от пар "смещение, длина".

Ещё большая степень сжатия получается при использовании алгоритмов типа LZW. Описанные ранее алгоритмы имеют фиксированный размер окна, что приводит к невозможности занесения в словарь фраз длиннее размера окна. В алгоритмах LZW ( и их предшественнике LZ78 ) просмотровое окно имеет неограниченный размер, а словарь накапливает фразы (а не совокупность символов, как ранее ). Словарь имеет неограниченную длину, а кодер (декодер) работают в режиме ожидания фразы. Когда фраза, совпадающая со словарём, сформирована, выдаётся код совпадения (т.е. код этой фразы в словаре ) и код следующего за ней символа. Если по мере накопления символов образуется новая фраза, она также заносится в словарь, как и более короткая. В результате образуется рекурсивная процедура, обеспечивающая быстрое кодирование и декодирование.

Дополнительную возможность компрессии обеспечивает сжатое кодирование повторяющихся символов. Если в последовательности некоторые символы следуют подряд (например, в тексте это могут быть символы "пробел", в числовой последовательности - подряд идущие нули и т.д.), то имеет смысл заменять их парой "символ; длина" или "признак, длина". В первом случае в коде указывается признак, что будет осуществляться кодирование последовательности (обычно 1 бит ), потом код повторяющегося символа и длина последовательности. Во втором случае (предусмотренном для наиболее часто встречающихся повторяющихся символов ) в префиксе указывается просто признак повторов.