Изменения

<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>, содержащий еще не закодированные символы. Как правило, размер окна {{---}} несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент заключается в замене повторений на ссылки на позиции в словаретексте, который совпадает с содержанием буферагде такие подстроки уже встречались.

Алгоритм LZ77 выдает кодыИнформацию о повторении можно закодировать парой чисел {{---}} смещением назад от текущей позиции (<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, которая соответствует содержанию буфера;*длина подстроки;*length, next \rangle</tex>. В дополнение к двум уже описанным элементам, новый параметр <tex>next</tex> означает первый символ в буфере после подстрокинайденного совпадающего фрагмента. Если <tex>\mathrm{LZ77}</tex> не удалось найти совпадение, то считается, что <tex>offset = length = 0</tex>.

После этого [[Файл: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> (например, «вернись на <tex>2</tex> символа назад и выведи <tex>10</tex> символов»). Это означает, что подстрока будет повторяться несколько раз так, чтобы каждый символ совпадал с символом, стоящим на <tex>2</tex> позиции раньше, и всего добавилось <tex>10</tex> символов. Например: <tex>hello\langle 2, 10 \rangle \Leftrightarrow hello\boldsymbol{lololololo}</tex>. Символ всегда можно определить однозначно, даже если он отсутствует в буфере. === Реализация === Хранить результат кодирования будем в списке структур следующего вида: <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 += length ans.push({offset, length, s[pos]}) <font color=green>// добавляем в ответ очередной блок</font> '''return''' ans</code>

 Рассмотрим пример кодирования <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> с [[Алгоритм Хаффмана|}алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы. 

* если последовательность находится === Идея алгоритма ===Алгоритм <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 = "" <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({---dict[buffer], s[i]}} дополненная версия последовательности из словаря, то эта последовательность добавляется ) <font color=green>// добавляем пару в ответ</font> dict[buffer + s[i]] = dict.length + 1 <font color=green>// добавляем слово в словарь</font> buffer = "" <font color=green>// сбрасываем буфер</font> '''return''' ans</code>

В этот раз для примера возьмем строку <tex>abacababacabc</tex>. {| class="wikitable"! Словарь || Осталось обработать || Найденный префикс || Код || Примечание|-| <tex>\varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0, a \rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>|-| <tex>a</tex> || <tex>bacababacabcb</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://acy-books.ru/?p=62 Алгоритм LZ78]* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78 (LZ78)] [[Категория: Дискретная математика и алгоритмы]] [[Категория: Алгоритмы сжатия ]]