Алгоритмы LZ77 и LZ78 - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:12Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:29, 1 сентября 2022

2022-09-01T06:29:42Z

178.94.18.98: offset > length !!!!

2020-04-21T10:04:16Z

offset > length !!!!

Ortyomka: /* Реализация */

2019-10-08T09:04:53Z

‎Реализация

Ortyomka: /* Реализация */

2019-10-08T08:39:43Z

‎Реализация

Ortyomka: /* Реализация */

2019-10-08T08:26:24Z

‎Реализация

Condiamond: /* "Пример." Исправлена опечатка в ячейке второго столбца ("Осталось обработать") третьей строки - убран последний символ "b". */

2019-01-06T21:59:55Z

‎"Пример." Исправлена опечатка в ячейке второго столбца ("Осталось обработать") третьей строки - убран последний символ "b".

Nsychev в 13:11, 2 января 2018

2018-01-02T13:11:13Z

Nsychev: rewrite

2018-01-02T13:08:56Z

rewrite

Внесённые изменения

Yulya3102 в 19:25, 10 апреля 2012

2012-04-10T19:25:37Z

@@ Строка 1: / Строка 1: @@
 <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]] и другие. Оба приведенных алгоритма используют словарный подход.
@@ Строка 108: / Строка 87: @@
 === Модификации ===
-Известно много различных модификаций алгоритма <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>\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> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.

@@ Строка 1: / Строка 1: @@
 <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]] и другие. Оба приведенных алгоритма используют словарный подход.
@@ Строка 87: / Строка 108: @@
 === Модификации ===
-Известно много различных модификаций алгоритма <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>\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> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.

@@ Строка 58: / Строка 58: @@
 | <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>\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> её не находит

@@ Строка 125: / Строка 125: @@
       '''if''' not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font>
           last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font>
-          buffer = buffer.pop() <font color=green>// удаляем последний символ из буфера</font>
+          buffer.pop() <font color=green>// удаляем последний символ из буфера</font>
           ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font>
       '''return''' ans

@@ Строка 123: / Строка 123: @@
               dict[buffer + s[i]] = dict.length + 1   <font color=green>// добавляем слово в словарь</font>
               buffer = ""                             <font color=green>// сбрасываем буфер</font>
-      '''if''' buffer != "": <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font>
+      '''if''' not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font>
-          last_ch = buffer[-1] <font color=green>// берем последний символ буффера, как "новый" символ</font>
+          last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font>
-          buffer = buffer[:-1] <font color=green>// удаляем последний символ из буфера</font>
+          buffer = buffer.pop() <font color=green>// удаляем последний символ из буфера</font>
           ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font>
       '''return''' ans

@@ Строка 135: / Строка 135: @@
 | <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>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>

← Предыдущая		Версия 13:11, 2 января 2018
Строка 187:		Строка 187:
	* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]		* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
	* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]		* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]
		+
		+	[[Категория: Дискретная математика и алгоритмы]]
		+	[[Категория: Алгоритмы сжатия]]

@@ Строка 1: / Строка 1: @@
-LZ77 и LZ78 - алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы - самые известные варианты в семье LZ*, которая также включает LZW, LZSS, LZMA и другие алгоритмы.
+LZ77 и LZ78 {{---}} алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы {{---}} самые известные варианты в семье LZ*, которая также включает LZW, LZSS, LZMA и другие алгоритмы.
-Оба алгоритма - алгоритмы со словарным подходом. Алгоритм LZ77 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78.
+Оба алгоритма {{---}} алгоритмы со словарным подходом. Алгоритм LZ77 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78.
 == LZ77 ==
@@ Строка 6: / Строка 6: @@
 LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы достигнуть сжатия, алгоритм пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря.
-В качестве модели данных LZ77 использует "скользящее" по сообщению окно, разделенное на две неравных части. Первая часть, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, - буфер, содержащий еще не закодированные символы. Как правило, размер окна - несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буфера.
+В качестве модели данных LZ77 использует "скользящее" по сообщению окно, разделенное на две неравных части. Первая часть, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, {{---}} буфер, содержащий еще не закодированные символы. Как правило, размер окна {{---}} несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буфера.
 Алгоритм LZ77 выдает коды, состоящие из трех элементов:
@@ Строка 50: / Строка 50: @@
 * если последовательность находится в словаре, то на выход подается код для этой записи
-* если последовательность - дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь
+* если последовательность {{---}} дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь
 Например, если в словаре уже хранится последовательность ''ABC'', и программа встречает последовательность ''ABCA'', то на выход сначала подается код из словаря для ''ABC'', затем символ ''A'', а затем последовательность ''ABCA'' будет добавлена в словарь. Если потом встретится последовательность ''ABCAB'', на выход подастся код для ''ABCA'', символ ''B'', и в словарь добавится ''ABCAB''. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет в словарь новую последовательность, которая на один байт длиннее.
@@ Строка 91: / Строка 91: @@
 * [http://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]
 * [http://ru.wikipedia.org/wiki/LZ77 Соответствующая статья в википедии(Алгоритм LZ77 описан по-другому) ]
-* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. - Экономное кодирование дискретной информации]
+* [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://acy-books.ru/?p=62 Алгоритм LZ78]