Идея алгоритма Лемпеля-Зива, Алгоритм LZ77 - Анализ алгоритма Лемпеля-Зива

Основная идея алгоритма Лемпеля-Зива состоит в замене появления фрагмента в данных (группы байт) ссылкой на предыдущее появление этого фрагмента. Существуют два основных класса методов, названных в честь Якоба Зива (Jakob Ziv) и Абрахама Лемпеля (Abraham Lempel), впервые предложивших их в 1977 (алгоритм LZ77) и 1978 годах (алгоритм LZ78).

Алгоритм LZ77

LZ77 [2] использует уже просмотренную часть сообщения как словарь. Чтобы добиться сжатия, он пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря. Алгоритм LZ77 предлагает оригинальное решение для устройства словаря. Вместо построения словаря для хранения фрагментов в виде отдельной структуры данных LZ77 предлагает использовать предшествующий фрагмент исходных данных конечной длины как готовый словарь.

Метод LZ77 оперирует двумя элементами данных:

    1) Буфер предыстории - уже обработанный фрагмент исходных данных фиксированной длины; 2) Буфер предпросмотра - еще не обработанный фрагмент данных, следующий за буфером предыстории.

Метод LZ77 пытается найти в буфере предыстории, фрагмент текста максимальной длины из буфера предпросмотра и когда это удается, то на выход выдается пара значений, соответствующая позиции фрагмента в буфере предыстории и длине фрагмента, иначе выводится первый символ буфера предпросмотра и повторяется попытка поиска для следующего фрагмента. В упрощенном виде алгоритм можно записать, как это показано на рис.1.

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

упрощенный алгоритм кодирования lz77

Рис. 1. Упрощенный алгоритм кодирования LZ77

LZ77 передвигает окно фиксированного размера (буфер предыстории) по данным. Очевидно, что наилучшего результата можно было бы достичь, если бы буфер предыстории был бы по размеру равен данным, но на практике используют ограниченный буфер (обычно16 или32 кБайт). Это обусловлено, как очевидными ограничениями по размерам ОЗУ, так и необходимостью ограничить время поиска фрагмента в буфере.

Поскольку метод не требует построения словаря, а для поиска фрагмента в буфере существуют очень эффективные алгоритмы, то LZ77 широко применяется на практике. Большинство коммерческих архиваторов (ace, arj, lha, zip, zoo) являются комбинацией LZ77 и метода Хаффмана (или арифметического кодирования). Наиболее используемые алгоритмы происходят от метода LZSS, описанного Джеймсом Сторером (James Storer) и Томасом Шимански (Thomas Szymanski) в 1982 г.

Похожие статьи




Идея алгоритма Лемпеля-Зива, Алгоритм LZ77 - Анализ алгоритма Лемпеля-Зива

Предыдущая | Следующая