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

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

Общая схема алгоритма LZ77 такова (это не точное описание алгоритма):

• входные данные читаются последовательно, текущая позиция условно разбивает массив входных данных на прочитанную и непрочитанную части;

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в прочитанной части. Если совпадение найдено, то составляется комбинация {смещение, длина}, где смещение указывает, на сколько байтов надо сместиться назад от текущей позиции, чтобы найти совпадение, а длина — это длина совпадения;

• если запись комбинации {смещение, длина} короче совпадения, то она записывается в выходной массив, а текущая позиция перемещается вперед (на длину совпадающей части);

• если совпадение не обнаружено или оно короче записи комбинации {смещение, длина}, то в выходной массив копируется текущий байт, текущая позиция перемещается вперед на 1, и анализ повторяется.

Пример. Фраза КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ зако- дируется алгоритмом LZ77 как КО ЛО(-4,3)_(- 5,4 )0_(-14,7)ЬНИ.

Общая схема алгоритма LZ78 такова (это не точное описание алгоритма):

• алгоритм во время сжатия текста создает специаль­ный словарь повторяющихся цепочек, в словаре каждой цепочке соответствует короткий код;

• для цепочки первых байтов непрочитанной части ищется наиболее длинное совпадение в словаре. Код совпадения записывается в выходной массив, туда же заносится первый несовпавший символ, и текущая позиция перемещается вперед на длину совпадения + 1;

• в словарь добавляется новое слово: «совпадение» + + «несовпавший символ», и процесс повторяется до тех пор, пока не будет сжат весь входной массив.

Алгоритмы Лемпеля - Зива тем лучше сжимают текст, чем больше размер входного массива. Характерной особенностью обратных алгоритмов LZ77 и LZ78 является то, что, кроме самих сжатых данных, никакой дополнительной информации им не требуется! Начав работать, эти алгоритмы по уже распакованной части восстанавливают информацию, необходимую для распаковки следующих частей сжатых данных. Для сравнения: в алгоритме Хаффмана вместе со сжатыми данными требуется сохранять дерево Хаффмана, иначе распаковка будет невозможна.

Поучительна история развития алгоритмов Лемпеля - Зива. Зив и Лемпель придумали плодотворные идеи сжатия, построили алгоритмы и провели теоретическое исследование их эффективности. Но поскольку опубликованные алгоритмы были очень неэффективно реализованы (т. е. запрограммированы), долгое время они не использовались на практике. Только спустя 6 лет, в 1984 году Терри Велч (Terry Welch) сумел существенно улучшить алгоритм LZ78. Эта модификация алгоритма получила название LZW, она широко используется в программах сжатия данных. Алгоритм LZ77 ждал своего часа целых десять лет — только в 1987 году появилась его высокоэффективная версия, которая работала в сотни (!) раз быстрее оригинального алгоритма. В настоящее время существует около полусотни модификаций обоих алгоритмов. Обобщенно все они называются методами сжатия со словарем. Эти алгоритмы оказались настолько быстры и эффективны, что сейчас занимают лидирующее место среди используемых на практике алгоритмов сжатия.