Изменения

Перейти к: навигация, поиск

Алгоритмы LZ77 и LZ78

8371 байт добавлено, 12:04, 8 октября 2019
м
Реализация
'''<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используют словарный подход.
== LZ77 ==
Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в [[RLE]].
=== Принципы работи алгоритма ===
Основная суть алгоритма - ето замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхождения.
Для етого используют метод скользящего окна.
Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).
Скользящее окно можно представить в видединамической структуры данных который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.
Рассмотрим последовательность из N элементов.
В стандартном алгоритме LZ77 совпадения строки кодируются парой:* длина совпадения (match length)* смещение (offset) или дистанция (distance)Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в словаре на ''значение смещения'' символов и скопировать ''значение длины'' символов, начиная с текущей позиции».Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары ''длина-смещение'' является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.=== Описания Идея алгоритма===В кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <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> кодирует ссылки блоками из трёх элементов {{| border="2" | class="wikitable" |Содержымое окна |Содержимое буфера |КОД |- |'--}} <tex>\langle offset, length, next \rangle</tex>.В дополнение к двум уже описанным элементам, новый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента.Если <tex>\mathrm{LZ77}</tex> не удалось найти совпадение, то считается, что <tex>offset = length = 0</tex>...'( |Ячейка 2*2 |Ячейка 3*2 |- |Ячейка 1*3 |Ячейка 2*3 |Ячейка 3*3 |}
Поз[[Файл:LZ77-simple-example. Длина Симв. ''mississippi '' 0 0 a a ''bracadabra'' 0 0 b ab ''racadabra'' 0 0 r '''a'''br ''acadabra'' 3 1 c abr'''a'''c ''adabra'' 2 1 d '''abra'''cad ''abra'' 7 4 abrajpg]]
Для эффективного поиска повторов в <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>. Квадратом обведен буфер. {| class="wikitable"!Строка || Совпадение || Закодированная последовательность || Примечание|-| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст|-| <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, b \rangle</tex> || В буфере нет <tex>b</tex>|-| <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || |-| <tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7, d \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> её не содержит этой информациинаходит|-| <tex>abacabaca\fbox{$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</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>. === Декодирование ===Для декодирования <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>\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> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.
Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they output their encoded data — what values are possible for lengths and distances, for example, and how length-distance pairs are distinguished from ''literals'' (single characters encoded as themselves, rather than as part of a length-distance pair.) A few examples:
* The algorithm illustrated in Lempel and Ziv’s original 1977 paper output all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal which followed that match. If two successive characters in the input stream could only be encoded as literals, the length would be 0.
* In the [[PalmDoc]] format, a length-distance pair is always encoded by a two-byte sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding the distance, 3 go to encoding the length, and the remaining two are used to make sure the decoder can identify the first byte as the beginning of such a two-byte sequence.
* [[As of 2004]], the most popular LZ77 based compression method is called [[DEFLATE (algorithm)|DEFLATE]]; it combines LZ77 with [[Huffman coding]]. Literals, lengths, and a symbol to indicate the end of the current block of data are all placed together into one alphabet. Distances can be safely placed into a separate alphabet; since a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice-versa.
-->
== LZ78 ==
В отличие от LZ77=== Идея алгоритма ===Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, работающего с уже полученными даннымигенерируя временный словарь во время кодирования и декодирования. Изначально словарь пуст, LZ78 ориентируется на данныеа алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, которые только пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут получены состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (LZ78 не использует «скользящее» окно<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> '''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>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>.
== Ссылки См. также ==* Jacob Ziv, Abraham Lempel. [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf A Universal Algorithm for Sequential Data Compression[Алгоритм RLE]] IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.* [http://www.binaryessence.com/dct/en000138.htm Пример работы алгоритма LZ77 (см. example "abracadabra")[Алгоритм LZW]]* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/ Описание алгоритма LZ77 в курсе лекций по теории кодирования информации[Алгоритм LZSS]]* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/2.html Описание алгоритма LZ78 в курсе лекций по теории кодирования информации[Алгоритм LZMA]]
{{compu-stub}}== Примечания =={{методы сжатия}}<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:Алгоритмы сжатия без потерь//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]
[[csКатегория:LZ77Дискретная математика и алгоритмы]][[deКатегория:LZ77]][[en:LZ77 and LZ78]][[et:LZ77]][[fr:LZ77 et LZ78]][[hu:LZ77]][[it:LZ77 e LZ78]][[ja:LZ77]][[pl:LZ77]][[pt:LZ77]][[zh:LZ77与LZ78Алгоритмы сжатия]]
3
правки

Навигация