Изменения

'''<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|LZW]], [[Алгоритм_LZSS|LZSS]], [[Алгоритм_LZMA|LZMA ]] и другие алгоритмы.Оба приведенных алгоритма относятся к словарным методам. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78используют словарный подход. 

Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в [[RLE]].=== Принципы работы Идея алгоритма ===Основная суть алгоритма - это замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхожденияВ кодируемых строках часто содержатся совпадающие длинные подстроки.Для этого используют метод скользящего окна.Скользящее окно можно представить Идея, лежащая в виде динамической структуры данных который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.Таким образом, сам процесс сжимающего кодирования согласно основе <tex>\mathrm{LZ77 напоминает написание программы}</tex>, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять заключается в замене повторений на ссылки на эти значения позиции в «скользящем окне»тексте, где такие подстроки уже встречались.В стандартном алгоритме LZ77 совпадения строки кодируются Информацию о повторении можно закодировать парой:* длина совпадения (match length)* смещение чисел {{---}} смещением назад от текущей позиции (<tex>offset</tex>) или дистанция и длиной совпадающей подстроки (distance<tex>length</tex>)Кодируемая пара трактуется именно . В таком случае, например, строка <tex>pabcdeqabcde</tex> может быть представлена как команда копирования символов из скользящего окна с определенной позиции<tex>pabcdeq \langle 6, 5 \rangle</tex>. Выражение <tex>\langle 6, или дословно как: «Вернуться в словаре 5 \rangle</tex> означает «вернись на ''значение смещения'' <tex>6</tex> символов назад и скопировать ''значение длины'' символоввыведи <tex>5</tex> символов». Алгоритм <tex>\mathrm{LZ77}</tex> кодирует ссылки блоками из трёх элементов {{---}} <tex>\langle offset, length, начиная с текущей позиции»next \rangle</tex>.Особенность данного алгоритма сжатия заключается в томВ дополнение к двум уже описанным элементам, что использование кодируемой пары ''длина-смещение'' является новый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента. Если <tex>\mathrm{LZ77}</tex> не только приемлемымудалось найти совпадение, но и эффективным в тех случаяхто считается, когда значение длины превышает значение смещениячто <tex>offset = length = 0</tex>. [[Файл:LZ77-simple-example.jpg]] Пример с командой копирования Для эффективного поиска повторов в <tex>\mathrm{LZ77}</tex> применяется метод «скользящего окна» {{---}} совпадения ищутся не совсем очевиден: «Вернуться на 1 символ назад всём обработанном префиксе, а в небольшом буфере и скопировать 7 , состоящем из последних обработанных символов. Обычно длина буфера равна <tex>2</tex>, начиная с текущей позиции»<tex>4</tex> или <tex>32 \mathrm{KB}</tex>. Каким Таким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары при больших объемах ввода алгоритм тратит меньше времени за счет того, что просматривается не вся исходная строка. С другой стороны, слишком маленькая длина словаря может прояснить ситуацию: каждые 7 последующих символов совпадают привести к тому, что расположенные далеко друг от друга совпадения (эквивалентнына большем расстоянии, чем длина словаря) с 1 символом перед нимине будут учтены, и кодирование станет менее оптимальным. Также нетривиальным может оказаться то, что при кодировании <tex>\mathrm{LZ77}</tex> значение <tex>offset</tex> может быть меньше, чем <tex>length</tex> (например, «вернись на <tex>2</tex> символа назад и выведи <tex>10</tex> символов»). Это означает, что подстрока будет повторяться несколько раз так, чтобы каждый символ совпадал с символом, стоящим на <tex>2</tex> позиции раньше, и всего добавилось <tex>10</tex> символов. Например: <tex>hello\langle 2, 10 \rangle \Leftrightarrow hello\boldsymbol{lololololo}</tex>. Символ всегда можно определить однозначно определить, переместившись назад в буфере — даже если данный символ еще он отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''. === Описания алгоритмаРеализация ===LZ77 использует "скользящее" по сообщению окноХранить результат кодирования будем в списке структур следующего вида: <code> '''struct''' Node: '''int''' offset '''int''' length '''char''' next</code> Функция <code>findMatching</code> ищет в буфере строку, совпадающую с префиксом суффикса строки <tex>s</tex>, начинающегося с символа <tex>pos</tex> и возвращает искомую пару <tex>\langle offset, length \rangle</tex>. Допустим  Функция <code>shiftBuffer</code> сдвигает буфер вперёд на текущей итерации окно зафиксировано<tex>x</tex> символов. С правой стороны окна наращиваем подстроку пока она есть в строке скользящее окно + наращиваемая  <code> <font color=green>// <tex>s</tex> {{---}} исходная строка и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий из трех элементов // функция возвращает список блоков <tex>\langle offset, length, next \rangle</tex></font> '''list<Node>''' encodeLZ77('''string''' s):* смещение в окне; '''list<Node>''' ans = []* длина буфера; pos = 0* последний символ буфера '''while''' pos < s.length:В конце итерации алгоритм сдвигает offset, length = findMatching(buffer, pos) <font color=green>// ищем слово в словаре</font> shiftBuffer(length + 1) <font color=green>// перемещаем скользящее окно на длину равную длине буфера</font> pos +1= length ans.push({offset, length, s[pos]}) <font color=green>// добавляем в ответ очередной блок</font> '''return''' ans</code> === Пример "kabababababz" === Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</tex>. Квадратом обведен буфер. {| borderclass="1wikitable" !Содержимое окна(длина равна 4)Строка || Совпадение || Закодированная последовательность || Примечание !Содержимое буфера|- !КОД| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст |- |'' <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} |'k' |<tex>\langle 0,0,'k'b \rangle</tex> || В буфере нет <tex>b</tex> |- |'k' <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || |'a'- |<0tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7,0d \rangle</tex> || Здесь выгодно сделать так,'что <tex>offset < length</tex>|-| <tex>abacaba\fbox{$cabad$}aca</tex> || <tex>a'</tex> || <tex>\langle 2, 1, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex>её не находит |- |'ka'<tex>abacabaca\fbox{$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</tex> ставим символ конца строки |'b'}  |Результатом кодирования является список полученных троек: <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>. === Декодирование ===Для декодирования <tex>\mathrm{LZ77}</tex> необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность, затем следующий символ. Псевдокод этого алгоритма: <code> |<font color=green>// <tex>encoded</tex> {{---}} список блоков <tex>\langle offset, length, next \rangle</tex> |// функция возвращает декодированную строку</font> '''string''' decodeLZ77('''list<Node>''kab'encoded): | ans = "" '''for''' node '''in''aba'encoded: |<2,2, '''if''a'node.length > 0: <font color=green>// если необходим повтор</font> | start = ans.length -node.offset <font color=green>// возвращаемся на <tex>offset</tex> символов назад</font> | '''for''baba'i = 0 .. node.length - 1: <font color=green>// добавляем <tex>length</tex> символов</font> | ans += ans[start + i] ans += node.next <font color=green>// добавляем следующий символ</font> '''return''bababz'ans |<2/code> === Модификации ===Известно много различных модификаций алгоритма <tex>\mathrm{LZ77}</tex>. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно {{---}} пары <tex>\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}</tex> и хранит однобитный флаг,5показывающий,'z'какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>\mathrm{PalmDoc}</tex><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> с [[Алгоритм Хаффмана|}алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы. 

=== Пример "kabababababz" Идея алгоритма ===Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования. Изначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {| border{---}} номера в словаре самого длинного найденного префикса (<tex>pos</tex>) и символа, который идет за этим префиксом (<tex>next</tex>). При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа. === Реализация ==="1"  Будем хранить результат кодирования в такой структуре: <code> !Содержимое '''struct''' Node: '''int''' pos <font color=green>// номер слова в словаре</font> '''char''' next</code> В качестве словарябудем использовать обычный <code>map</code>: !Содержимое считываемая строка !КОД <code> |-'''list<Node>''' encodeLZ78('''string''' s): | '''string'''buffer = "" <font color=green>// текущий префикс</font> | '''map<string, int>''k'dict = {} <font color=green>// словарь</font> | '''list<Node>''' ans = [] <font color=green>// ответ</font> '''for''' i = 0,.. s.length - 1: '''if''k'dict.hasKey(buffer + s[i]): <font color=green>// можем ли мы увеличить префикс</font> |- buffer += s[i] | '''else''k' : | ans.push({dict[buffer], s[i]}) <font color=green>// добавляем пару в ответ</font> dict[buffer + s[i]] = dict.length + 1 <font color=green>// добавляем слово в словарь</font> buffer = "" <font color=green>// сбрасываем буфер</font> '''if''a'not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font> | last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font> buffer.pop() <font color=green>// удаляем последний символ из буфера<0/font> ans.push({dict[buffer],last_ch}) <font color=green>// добавляем пару в ответ</font> '''return''a'ans</code> === Пример === В этот раз для примера возьмем строку <tex>abacababacabc</tex>. {| class="wikitable"! Словарь || Осталось обработать || Найденный префикс || Код || Примечание|- |'k'<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> || |- |<0tex>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> |- |'k'<tex>a</tex>, <tex>b</tex>,'<tex>ac</tex> || <tex>ababacabc</tex> || <tex>a'</tex> || <tex>\langle 1,'b'\rangle</tex> || |'ab'- |<2tex>a</tex>,'<tex>b'</tex>, <tex>ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab</tex> || <tex>\langle 4, a \rangle</tex>|| |- |'k','<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> |'k','astring''',decodeLZ78('b','ablist<Node>','aba'encoded): | ''ba' |list<3,string>''а'dict = [""] <font color=green> |// словарь, слово с номером 0 {{---}} пустая строка</font> | '''string''k',ans = "" <font color=green>// ответ</font> 'a','bfor','ab',node 'aba','bain' |'abab'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'3,'z'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://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]* [http://mf.wikipediagrsu.orgby/wikiUchProc/LZ77 Соответствующая статья в википедии(livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77 описан по другому) ]* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы сжатия]]