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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:29:33Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:44, 1 сентября 2022

2022-09-01T04:44:25Z

Shersh: /* Организация поиска в словаре */

2014-11-15T19:26:26Z

‎Организация поиска в словаре

Shersh: /* Пример */

2014-11-15T19:21:50Z

‎Пример

Shersh: /* Пример */

2014-11-15T19:21:35Z

‎Пример

Shersh: /* Пример декодирования */

2014-11-15T19:20:20Z

‎Пример декодирования

Shersh: /* Реализация "скольжения" */

2014-11-15T19:15:28Z

‎Реализация "скольжения"

109.205.252.36: /* Пример */

2014-11-15T17:54:43Z

‎Пример

109.205.252.36: /* Пример */

2014-11-10T19:35:37Z

‎Пример

109.205.252.36: /* Пример кодирования */

2014-11-10T19:32:12Z

‎Пример кодирования

← Предыдущая		Версия 16:29, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	Эта версия [[Алгоритмы LZ77 и LZ78\|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:		Эта версия [[Алгоритмы LZ77 и LZ78\|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
	*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь\|очереди]]		*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь\|очереди]]

← Предыдущая		Версия 04:44, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	Эта версия [[Алгоритмы LZ77 и LZ78\|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:		Эта версия [[Алгоритмы LZ77 и LZ78\|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
	*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь\|очереди]]		*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь\|очереди]]

@@ Строка 13: / Строка 13: @@
 ===Организация поиска в словаре===
-Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части, размером длины буфера.
+Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части размером длины буфера.
 ====Порядок изменения дерева поиска====
 Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.

@@ Строка 46: / Строка 46: @@
 '''Таблицы 1 и 2. Строки по пять символов.'''
 {|
+   |

@@ Строка 44: / Строка 44: @@
 Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
 {|
@@ Строка 128: / Строка 130: @@
   |}
 |}
 Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
@@ Строка 146: / Строка 144: @@
 С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
 Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.
-В данном примере длина буфера - <tex>5</tex> символов, часть совпадения - <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
+В данном примере длина буфера {{---}} <tex>5</tex> символов, часть совпадения {{---}} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
 ===Оптимизация памяти===

@@ Строка 184: / Строка 184: @@
 ===Пример декодирования===
-LZSS, длина словаря — 8 байт (символов). Коды сжатого сообщения —
+LZSS, длина словаря — <tex>8</tex> байт (символов). Коды сжатого сообщения —
 [[Файл:Кодисходного_сообщения_png.png‎ ]]

@@ Строка 7: / Строка 7: @@
 ===Реализация "скольжения"===
-Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]],в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
+Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
 Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.

@@ Строка 133: / Строка 133: @@
-Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
+Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
 Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <tex>L-1</tex>.
-В нашем примере длина совпадения равна 2, поэтому кодер выдает метку <tex>\langle</tex><tex>16,2</tex><tex>\rangle</tex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
+В нашем примере длина совпадения равна <tex>2</tex>, поэтому кодер выдает метку <tex>\langle</tex><tex>16,2</tex><tex>\rangle</tex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
 {| class="wikitable"

@@ Строка 167: / Строка 167: @@
 ===Пример кодирования===
 Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
-В данном примере один символ кодируется восемью битами. Поэтому после префикса 0 декодер считывает следующие 8 бит.
+В данном примере один символ кодируется восемью битами. Поэтому после префикса <tex>0</tex> декодер считывает следующие <tex>8</tex> бит.
-После префикса 1 хранится пара  <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex>. Так как смещение и длина не превосходят длины словаря, то размер пары <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex> равен удвоенному количеству бит, требуемых для хранения длины словаря.
+После префикса <tex>1</tex> хранится пара  <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex>. Так как смещение и длина не превосходят длины словаря, то размер пары <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex> равен удвоенному количеству бит, требуемых для хранения длины словаря.
-Длина словаря в данном примере 8. Поэтому после префикса 1 декодер считывает 6 бит.
+Длина словаря в данном примере <tex>8</tex>. Поэтому после префикса <tex>1</tex> декодер считывает <tex>6</tex> бит.