Изменения
offset > length !!!!
<tex>\mathrm{LZ77 }</tex> и <tex>\mathrm{LZ78 }</tex> {{- --}} алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля Абрахамом Лемпелем<ref>[https://en.wikipedia.org/wiki/Abraham_Lempel Wikipedia {{---}} Abraham Lempel]</ref> и Якоба Зива Якобом Зивом<ref>[https://en.wikipedia.org/wiki/Yaakov_Ziv Wikipedia {{---}} Yaakov Ziv]</ref> в <tex>1977 </tex> и <tex>1978 </tex> годахсоответственно. Эти алгоритмы - самые известные варианты в семье стали основой других алгоритмов семьи <tex>\mathrm{LZ*, которая также включает }</tex>: [[Алгоритм_LZW|LZW]], [[Алгоритм_LZSS|LZSS]], [[Алгоритм_LZMA|LZMA ]] и другие алгоритмы.Оба приведенных алгоритма - алгоритмы со словарным подходом. Алгоритм LZ77 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78используют словарный подход.
== LZ77 ==
=== Идея алгоритма === В качестве модели данных кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <tex>\mathrm{LZ77 использует "скользящее" по сообщению окно}</tex>, разделенное заключается в замене повторений на ссылки на две неравных части. Первая частьпозиции в тексте, большая по размеру, включает где такие подстроки уже просмотренную часть сообщения. Вторая, намного меньшая, - буфер, содержащий еще не закодированные символы. Как правило, размер окна - несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буферавстречались.
=== Пример ===
Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</tex>. Квадратом обведен буфер. {| borderclass="1wikitable" !СообщениеСтрока || Совпадение || Закодированная последовательность || Примечание !Подстрока|- !Код| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст |- |<tex>\fbox{kababa$a$}bababzbacabacabadaca</tex> | | {{---}} ||<tex>\langle 0,0,b \rangle</tex> || В буфере нет <tex>kb</tex>> |- |<tex>k\fbox{ababab$ab$}ababzacabacabadaca</tex>|| <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || |- |<0tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7,0d \rangle</tex> || Здесь выгодно сделать так,что <tex>aoffset < length</tex>> |- |<tex>kaabacaba\fbox{bababa$cabad$}babzaca</tex> || <tex>a</tex> | |<0tex>\langle 2,01,c \rangle</tex>b|| Последовательность <tex>aca</tex>уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex>её не находит |- |<tex>kababacabaca\fbox{ababab$badac$}abza</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>abnext</tex>ставим символ конца строки |} Результатом кодирования является список полученных троек: <tex>\left[ \langle 0, 0, a \rangle, \langle 0, 0, b \rangle, \langle 2,1, c \rangle, \langle 4, 7, d \rangle, \langle 2,1, c \rangle, \langle 2, 1, \varnothing \rangle \right]</tex>a. === Декодирование ===Для декодирования <tex>\mathrm{LZ77}</tex>необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность, затем следующий символ. Псевдокод этого алгоритма: <code> |<font color=green>// <tex>encoded</tex> {{---}} список блоков <tex>\langle offset, length, next \rangle</tex> // функция возвращает декодированную строку</font> |'''string''' decodeLZ77('''list<Node>''' encoded): ans = "" '''for''' node '''in''' encoded: '''if''' node.length > 0: <font color=green>// если необходим повтор</font> start = ans.length - node.offset <font color=green>// возвращаемся на <tex>offset</tex> символов назад</font> '''for''' i = 0 .. node.length - 1: <font color=green>// добавляем <tex>length</tex> символов</font> ans += ans[start + i] ans += node.next <font color=green>// добавляем следующий символ</font> '''return''' ans</code> === Модификации ===Известно много различных модификаций алгоритма <tex>kababa\fboxmathrm{bababzLZ77}</tex> |. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно {{---}} пары <tex>babab\langle offset, length \rangle</tex> |(length-distance pair<ref>[https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77 Wikipedia {{---}} LZ77]</ref>). [[Алгоритм LZSS]] является улучшением <tex>\mathrm{LZ77}<2/tex> и хранит однобитный флаг,5показывающий,какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>\mathrm{PalmDoc}</tex>z<ref>[https://wiki.mobileread.com/wiki/PalmDOC Описание формата PalmDOC]</ref> на каждую пару смещения и длины выделяется по <tex>2</tex>байта. Также на <tex>\mathrm{LZ77}</tex> основаны алгоритмы <tex>\mathrm{LZH}</tex><ref>[https://msdn.microsoft.com/en-us/library/hh554076.aspx LZH]</ref> и <tex>\mathrm{DEFLATE}</tex><ref>[https://en.wikipedia.org/wiki/DEFLATE Wikipedia {{---}} DEFLATE]</ref> (последний является широко используемым), которые совмещают <tex>\mathrm{LZ77}</tex> с [[Алгоритм Хаффмана|}алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.
== LZ78 ==
=== Пример ===
В этот раз для примера возьмем строку <tex>abacababacabc</tex>. {| class="wikitable"! Словарь || Осталось обработать || Найденный префикс || Код || Примечание|-| <tex>\varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0, a \rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>|-| <tex>a</tex> || <tex>bacababacabc</tex> || {{---}} || <tex>\langle 0, b \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \rangle</tex> || Нашелся префикс <tex>a</tex> (слова в словаре нумеруются с <tex>1</tex>), добавляем <tex>ac</tex>|-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex> || <tex>ababacabc</tex> || <tex>a</tex> || <tex>\langle 1, b \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab</tex> || <tex>\langle 4, a \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex> || <tex>cabc</tex> || {{---}} || <tex>\langle 0, c \rangle </tex> || |-| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex>, <tex>c</tex> || <tex>abc</tex> || <tex>ab</tex> || <tex>\langle 4, c\rangle </tex> || |} Результатом кодирования является список пар: <tex>\left[ \langle 0, a \rangle, \langle 0, b \rangle, \langle 1, c \rangle, \langle 1, b \rangle, \langle 4, a \rangle, \langle 0, c \rangle, \langle 4, c \rangle \right]</tex> = Ссылки ==Декодирование === Декодирование происходит аналогично кодированию, на основе декодируемой информации строим словарь и берем из него значения. <code> '''string''' decodeLZ78('''list<Node>''' encoded): '''list<string>''' dict = [""] <font color=green>// словарь, слово с номером 0 {{---}} пустая строка</font> '''string''' ans = "" <font color=green>// ответ</font> '''for''' node '''in''' encoded: word = dict[node.pos] + node.next <font color=green>// составляем слово из уже известного из словаря и новой буквы</font> ans += word <font color=green>// приписываем к ответу</font> dict.push(word) <font color=green>// добавляем в словарь</font> '''return''' ans</code> === Модификации ===Одна из главных проблем <tex>\mathrm{LZ78}</tex> {{---}} размер словаря. Он ничем не ограничен и может достигать огромных размеров на больших объемах входных данных. В различных модификациях установлены лимиты на размер словаря: при достижении определенного лимита словарь может «замораживаться» (в него перестают добавляться новые слова), из словаря могут удалять менее используемые или самые старые слова и так далее. Самой известной модификацией <tex>\mathrm{LZ78}</tex> является [[Алгоритм LZW|LZW]]. В нём есть две важных особенности. Первая {{---}} словарь изначально инициализирован всеми символами алфавита. Вторая {{---}} после нахождения максимального префикса поиск следующего префикса начинается не с символа после неподходящего, а с самого неподходящего символа. Это позволяет не выводить неподходящий символ, а выяснять его прямо из словаря. Эта модификация используется в том числе в изображениях в формате <tex>\mathrm{GIF}</tex><ref>[https://en.wikipedia.org/wiki/GIF Wikipedia {{---}} GIF]</ref>. == См. также ==* [[Алгоритм RLE]]* [[Алгоритм LZW]]* [[Алгоритм LZSS]]* [[Алгоритм LZMA]] == Примечания ==<references/> == Источники информации ==* [https://en.wikipedia.org/wiki/LZ77_and_LZ78 Wikipedia {{---}} LZ77 and LZ78]* [http://ru.wikipedia.org/wiki/LZ77 Википедия {{---}} LZ77]* [https://fenix.tecnico.ulisboa.pt/downloadFile/1407993358859638/Lempel_Ziv_by_Zeeh.pdf The Lempel Ziv Algorithm]
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]
* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]