Изменения

'''<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> это замена повторного вхождения строки ссылкой , заключается в замене повторений на ссылки на одну из предыдущих позиций вхожденияпозиции в тексте, где такие подстроки уже встречались.Для этого используют метод скользящего окна.Скользящее окно Информацию о повторении можно представить в виде динамической структуры данныхзакодировать парой чисел {{---}} смещением назад от текущей позиции (<tex>offset</tex>) и длиной совпадающей подстроки (<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, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программыlength, команды которой позволяют обращаться next \rangle</tex>. В дополнение к двум уже описанным элементам скользящего окна, и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в скользящем окненовый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента.В стандартном алгоритме Если <tex>\mathrm{LZ77 совпадения строки кодируются парой:* длина совпадения (match }</tex> не удалось найти совпадение, то считается, что <tex>offset = length)= 0</tex>.* смещение (offset) или дистанция (distance)Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как[[Файл: «Вернуться LZ77-simple-example.jpg]] Для эффективного поиска повторов в словаре <tex>\mathrm{LZ77}</tex> применяется метод «скользящего окна» {{---}} совпадения ищутся не на ''значение смещения'' символов и скопировать ''значение длины'' всём обработанном префиксе, а в небольшом буфере, состоящем из последних обработанных символов. Обычно длина буфера равна <tex>2</tex>, <tex>4</tex> или <tex>32 \mathrm{KB}</tex>. Таким образом, при больших объемах ввода алгоритм тратит меньше времени за счет того, начиная с текущей позиции»что просматривается не вся исходная строка.Особенность данного алгоритма сжатия заключается в томС другой стороны, слишком маленькая длина словаря может привести к тому, что использование кодируемой пары ''расположенные далеко друг от друга совпадения (на большем расстоянии, чем длина-смещение'' является словаря) не только приемлемымбудут учтены, но и эффективным в тех случаяхкодирование станет менее оптимальным. Также нетривиальным может оказаться то, когда что при кодировании <tex>\mathrm{LZ77}</tex> значение длины превышает значение смещения.Пример с командой копирования не совсем очевиден: «Вернуться <tex>offset</tex> может быть меньше, чем <tex>length</tex> (например, «вернись на 1 символ <tex>2</tex> символа назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентнывыведи <tex>10</tex> символов») с 1 символом перед ними.Это означает, что подстрока будет повторяться несколько раз так, чтобы каждый символ совпадал с символом, стоящим на <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> === Пример === Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>kabababababz5</tex> ===. Квадратом обведен буфер. {| borderclass="1wikitable" !Содержимое окнаСтрока || Совпадение || Закодированная последовательность || Примечание !Содержимое буфера|- !КОД |<tex>abacabacabadaca</tex> || {{--- }} ||<tex>kabababababz\langle 0, 0, a \rangle</tex>|| Буфер пуст|- |<tex>k\fbox{$a$}bacabacabadaca</tex> || {{---}} ||<tex>\langle 0,0,b \rangle</tex>k|| В буфере нет <tex>b</tex>> |- |<tex>kabababababz\fbox{$ab$}acabacabadaca</tex> ||<tex>a</tex>|| <tex>\langle 2, 1, c \rangle</tex> || |-| <tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> ||<0tex>\langle 4, 7,0d \rangle</tex> || Здесь выгодно сделать так,что <tex>aoffset < length</tex>> |- |<tex>kabababababzabacaba\fbox{$cabad$}aca</tex> ||<tex>ba</tex> ||<0tex>\langle 2,01,c \rangle</tex> || Последовательность <tex>baca</tex>уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex>её не находит |- |<tex>kabacabaca\fbox{ab$badac$}ababababza</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>abanext</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>kaba\fboxmathrm{bababLZ77}abz</tex> |. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно {{---}} пары <tex>\langle offset, length \rangle</tex>bababz(length-distance pair<ref>[https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77 Wikipedia {{---}} LZ77]</ref>). [[Алгоритм LZSS]] является улучшением <tex> |\mathrm{LZ77}<2/tex> и хранит однобитный флаг,5показывающий,какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>z\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> с [[Алгоритм Хаффмана|}алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы. 

=== Пример Идея алгоритма ===Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования. Изначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (<tex>pos</tex>) и символа, который идет за этим префиксом (<tex>kabababababznext</tex> ). При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа. === Реализация === Будем хранить результат кодирования в такой структуре: <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>''' dict = {| border} <font color=green>// словарь</font> '''list<Node>''' ans = [] <font color=green>// ответ</font> '''for''' i = 0 .. s.length - 1: '''if''' dict.hasKey(buffer + s[i]): <font color=green>// можем ли мы увеличить префикс</font> buffer += s[i] '''else''': ans.push({dict[buffer], s[i]}) <font color=green>// добавляем пару в ответ</font> dict[buffer + s[i]] = dict.length + 1 <font color=green>// добавляем слово в словарь</font> buffer ="1" <font color=green>// сбрасываем буфер</font> !Содержимое '''if''' not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font> last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font> buffer.pop() <font color=green>// удаляем последний символ из буфера</font> !Содержимое считываемой строки ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font> '''return''' ans</code> === Пример === В этот раз для примера возьмем строку <tex>abacababacabc</tex>. {| class="wikitable" !КОД Словарь || Осталось обработать || Найденный префикс || Код || Примечание |- |'' <tex>\varnothing</tex> ||<tex>kabacababacabc</tex> || {{---}} ||<tex>\langle 0,a \rangle</tex>k|| В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>> |- |<tex>ka</tex> ||<tex>abacababacabc</tex> || {{---}} ||<tex>\langle 0,b \rangle</tex> || |-| <tex>a</tex>, <tex>b</tex> |- |<tex>kacababacabc</tex>, || <tex>a</tex> ||<tex>b\langle 1, c \rangle</tex> || Нашелся префикс <0tex>a</tex> (слова в словаре нумеруются с <tex>1</tex>),добавляем <tex>bac</tex>> |- |<tex>ka</tex>, <tex>\fbox{a}b</tex>, <tex>bac</tex> ||<tex>abababacabc</tex> ||<2,tex>a</tex> || <tex>\langle 1, b\rangle</tex>>|| |- |<tex>ka</tex>, <tex>ab</tex>, <tex>bac</tex>, <tex>\fbox{ab}</tex> ||<tex>abaabacabc</tex> ||<4,tex>ab</tex> || <tex>\langle 4, a\rangle</tex>>|| |- |<tex>ka</tex>, <tex>ab</tex>, <tex>\fbox{b}ac</tex>, <tex>ab</tex>, <tex>aba</tex> ||<tex>bacabc</tex> |<3,| {{---}} || <tex>a\langle 0, c \rangle </tex>>|| |- |<tex>ka</tex>, <tex>ab</tex>, <tex>bac</tex>, <tex>ab</tex>, <tex>\fbox{aba}</tex>, <tex>bac</tex> ||<tex>abababc</tex> |<5,| <tex>bab</tex>> |- |<tex>k\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 = "" <texfont color=green>b// ответ</texfont>, '''for''' node '''in''' encoded: word = dict[node.pos] + node.next <texfont color=green>ab// составляем слово из уже известного из словаря и новой буквы</texfont>, ans += word <texfont color=green>aba// приписываем к ответу</texfont> dict.push(word) <font color=green>, // добавляем в словарь<tex/font>ba '''return''' ans</texcode>,  === Модификации ===Одна из главных проблем <tex>abab\mathrm{LZ78}</tex>{{---}} размер словаря. Он ничем не ограничен и может достигать огромных размеров на больших объемах входных данных. В различных модификациях установлены лимиты на размер словаря: при достижении определенного лимита словарь может «замораживаться» (в него перестают добавляться новые слова), из словаря могут удалять менее используемые или самые старые слова и так далее.  |Самой известной модификацией <tex>z\mathrm{LZ78}</tex> является [[Алгоритм LZW|<0LZW]]. В нём есть две важных особенности. Первая {{---}} словарь изначально инициализирован всеми символами алфавита. Вторая {{---}} после нахождения максимального префикса поиск следующего префикса начинается не с символа после неподходящего, а с самого неподходящего символа. Это позволяет не выводить неподходящий символ,а выяснять его прямо из словаря. Эта модификация используется в том числе в изображениях в формате <tex>z\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://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://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]