355
правок
Изменения
м
Нет описания правки
LZ77 и LZ78 {{- --}} алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы {{--- }} самые известные варианты в семье LZ*, которая также включает LZW, LZSS, LZMA и другие алгоритмы.Оба алгоритма {{--- }} алгоритмы со словарным подходом. Алгоритм LZ77 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78.
== LZ77 ==
LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы достигнуть сжатия, алгоритм пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря.
В качестве модели данных LZ77 использует "скользящее" по сообщению окно, разделенное на две неравных части. Первая часть, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, {{- --}} буфер, содержащий еще не закодированные символы. Как правило, размер окна {{--- }} несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буфера.
Алгоритм LZ77 выдает коды, состоящие из трех элементов:
* если последовательность находится в словаре, то на выход подается код для этой записи
* если последовательность {{- --}} дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь
Например, если в словаре уже хранится последовательность ''ABC'', и программа встречает последовательность ''ABCA'', то на выход сначала подается код из словаря для ''ABC'', затем символ ''A'', а затем последовательность ''ABCA'' будет добавлена в словарь. Если потом встретится последовательность ''ABCAB'', на выход подастся код для ''ABCA'', символ ''B'', и в словарь добавится ''ABCAB''. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет в словарь новую последовательность, которая на один байт длиннее.
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]
* [http://ru.wikipedia.org/wiki/LZ77 Соответствующая статья в википедии(Алгоритм LZ77 описан по-другому) ]
* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{- --}} Экономное кодирование дискретной информации]
* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
* [http://acy-books.ru/?p=62 Алгоритм LZ78]
