Изменения

'''<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> === Пример "kabababababz" === Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</tex>. Квадратом обведен буфер. {| borderclass="1wikitable" !Содержимое окна (длина равна 4) !Содержимое буфера !КОДСтрока || Совпадение || Закодированная последовательность || Примечание |- |'' <tex>abacabacabadaca</tex> || {{---}} |k |<tex>\langle 0,0,ka \rangle</tex>|| Буфер пуст |- |k <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} |a |<tex>\langle 0,0,ab \rangle</tex> || В буфере нет <tex>b</tex> |- |ka<tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || |b- |<0tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7,0d \rangle</tex> || Здесь выгодно сделать так,bчто <tex>offset > length</tex> |- |k<tex>abacaba\fbox{ab$cabad$}aca</tex> || <tex>a</tex> |aba |<tex>\langle 2,21, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна,aи <tex>\mathrm{LZ77}</tex>её не находит |- |kaba<tex>abacabaca\fbox{ba$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</tex>ставим символ конца строки |bababz} Результатом кодирования является список полученных троек: <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> |<2font color=green>// <tex>encoded</tex> {{---}} список блоков <tex>\langle offset,5length,znext \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>\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> и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <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> с [[Алгоритм Хаффмана|}алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы. 

=== Пример Идея алгоритма ===Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования. Изначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (<tex>pos</tex>) и символа, который идет за этим префиксом (<tex>next</tex>). При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа. === Реализация === Будем хранить результат кодирования в такой структуре: <code> '''struct''' Node: '''int''' pos <font color=green>// номер слова в словаре</font> '''char''' next</code> В качестве словаря будем использовать обычный <code>map</code>: <code> '''list<Node>''' encodeLZ78('''string''' s): '''string''' buffer = "kabababababz" <font color=green>// текущий префикс</font> '''map<string, int>''' dict = {} <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({| borderdict[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> === Пример === |k |В этот раз для примера возьмем строку <tex>abacababacabc<0,k/tex>.  {|-class="wikitable" ! Словарь || Осталось обработать || Найденный префикс || Код ||k Примечание |a- |<tex>\varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0,a\rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex> |- |k, <tex>a </tex> || <tex>bacababacabc</tex> || {{---}} |b |<tex>\langle 0,b\rangle</tex>|| |- |k<tex>a</tex>,<tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \fbox{rangle</tex> || Нашелся префикс <tex>a}</tex>(слова в словаре нумеруются с <tex>1</tex>), bдобавляем <tex>ac</tex> |ab- |<2tex>a</tex>, <tex>b</tex>, <tex>ac</tex> || <tex>ababacabc</tex> || <tex>a</tex> || <tex>\langle 1,b\rangle</tex>|| |- |k, <tex>a</tex>, <tex>b</tex>,<tex>\fbox{ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab}</tex> |aba |<tex>\langle 4,a\rangle</tex>|| |- |k, <tex>a</tex>,<tex>\fbox{b}</tex>,<tex>ac</tex>, <tex>ab</tex>, <tex>aba </tex> || <tex>cabc</tex> || {{---}} |ba |<3tex>\langle 0,аc \rangle </tex>|| |- |k, <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>,<tex>\fbox{aba}</tex>,ba <tex>c</tex> || <tex>abc</tex> || <tex>ab</tex> |abab |<5tex>\langle 4,bc\rangle </tex>|| |-}  |kРезультатом кодирования является список пар: <tex>\left[ \langle 0, a\rangle, \langle 0, b \rangle, \langle 1, c \rangle, \langle 1, b\rangle, \langle 4, a \rangle, ab\langle 0, abac \rangle, ba\langle 4, ababc \rangle \right]</tex> === Декодирование === Декодирование происходит аналогично кодированию, на основе декодируемой информации строим словарь и берем из него значения. <code> |z'''string''' decodeLZ78('''list<Node>''' encoded): | '''list<string>''' dict = [""] <font color=green>// словарь, слово с номером 0,z{{---}} пустая строка</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://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] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы сжатия]]