Алгоритм LZSS — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример кодирования)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 3 участников)
Строка 7: Строка 7:
  
 
===Реализация "скольжения"===
 
===Реализация "скольжения"===
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]],в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
+
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
  
 
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
 
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
Строка 13: Строка 13:
 
===Организация поиска в словаре===
 
===Организация поиска в словаре===
  
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части, размером длины буфера.  
+
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части размером длины буфера.  
 
====Порядок изменения дерева поиска====
 
====Порядок изменения дерева поиска====
 
Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
 
Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
Строка 45: Строка 45:
 
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
 
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
  
 +
'''Таблицы 1 и 2. Строки по пять символов.'''
 
{|
 
{|
 
   |
 
   |
Строка 129: Строка 130:
 
|}
 
|}
  
 
+
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
'''Таблицы 1 и 2. Строки по пять символов.'''
 
 
 
 
 
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
 
 
Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <tex>L-1</tex>.
 
Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <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"
 
{| class="wikitable"
Строка 145: Строка 142:
 
  |}
 
  |}
 
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
 
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
 +
Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.
 +
В данном примере длина буфера {{---}} <tex>5</tex> символов, часть совпадения {{---}} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
  
 
===Оптимизация памяти===
 
===Оптимизация памяти===
Строка 167: Строка 166:
 
===Пример кодирования===
 
===Пример кодирования===
 
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
 
Закодировать по алгоритму 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> бит.
  
  
Строка 182: Строка 181:
 
===Пример декодирования===
 
===Пример декодирования===
  
LZSS, длина словаря — 8 байт (символов). Коды сжатого сообщения —
+
LZSS, длина словаря — <tex>8</tex> байт (символов). Коды сжатого сообщения —
 
[[Файл:Кодисходного_сообщения_png.png‎ ]]  
 
[[Файл:Кодисходного_сообщения_png.png‎ ]]  
  

Текущая версия на 19:29, 4 сентября 2022

Эта версия алгоритма LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982. Базовый алгоритм был улучшен по трем направлениям:

  • буфер, содержащий еще не закодированные символы, сохраняется в циклической очереди
  • буфер поиска (словарь) хранитсяся в виде двоичного дерева поиска
  • метки имеют два поля, а не три

Модель данных

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

Как и в алгоритме LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.

Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.

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

Скорость кодирования LZ77 сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины [math]M[/math] (максимальная длина совпадения). В дереве хранятся все подстроки словарной части размером длины буфера.

Порядок изменения дерева поиска

Кодер изучает буфер поиска, создавая [math]T [/math] строк с числом символов [math]L[/math] , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями. На дереве все время находится одинаковое число [math]T [/math] узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, [math]T=S-L+1[/math].

Если во время кодирования случается совпадение длины [math]k[/math], то дерево надо перестроить путем удаления [math]k[/math] строк и добавления [math]k[/math] строк.

Удаляться будут первые [math]k[/math] строк буфера поиска до его сдвига, а добавляться будут последние [math]k[/math] строк этого буфера после сдвига.

Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних [math]L[/math] символов буфера поиска и добавить ее на дерево. Это следует повторить [math]k[/math] раз.

Для определения смещения уславливаемся, что:

  • нулевое смещение зарезервировали для обозначения конца кодирования;
  • если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.


Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.

Пример

Пусть входной файл содержит следующую последовательность: "sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из [math]16[/math]-байтного буфера поиска и [math]5[/math]-байтного буфера, содержащего еще не закодированные символы. После ввода первых [math]16+5[/math] символов скользящее окно выглядит так:

sid_eastman_clum sily_ teases_sea_sick_seals


причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.

Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как [math]12=16-5+1[/math]), которые помещены на двоичное дерево поиска вместе с их смещениями.

Таблицы 1 и 2. Строки по пять символов.

Таблица 1
sid_e 16
id_ea 15
d_eas 14
_east 13
eastm 12
astma 11
stmаn 10
tman_ 09
man_c 08
an_cl 07
n_clu 06
_clum 05
Таблица 2
d_eas 16
_east 15
eastm 14
astma 13
stmаn 12
tman_ 11
man_c 10
an_cl 09
n_clu 08
_clum 07
clums 06
lumsi 05

Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями [math]16[/math] и [math]10[/math], но первая из них, sid_e, имеет более длинное совпадение. Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть [math]L-1[/math].

В нашем примере длина совпадения равна [math]2[/math], поэтому кодер выдает метку [math]\langle[/math][math]16,2[/math][math]\rangle[/math]. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

si d_eastman_clumsi ly_te ases_sea_sick_seals

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2). Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения. В данном примере длина буфера — [math]5[/math] символов, часть совпадения — [math]2[/math] символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит [math]2[/math]. Это смещения [math]5[/math] и [math]6[/math]. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.

Оптимизация памяти

У алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма.

Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением "0" для незакодированных символов и "1" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

Кодер LZSS

Инициализация

Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.

Основной цикл работы

Алгоритм последовательно выполняет следующие действия:

  1. Кодирует содержимое буфера.
  2. Считывает очередные символы в буфер, удаляя при необходимости наиболее "старые" строки из словаря.
  3. Вставляет в дерево новые строки, соответствующие считанным символам.

Завершение работы

Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения.

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

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


540e164e73fca7dcfc2b6c970b135e24.png

Декодер LZSS

Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.

Декодер читает один бит сжатой информации и решает — это символ или пара [math]\langle[/math][math]offset,length[/math][math]\rangle[/math]. Если это символ, то следующие [math]8[/math] бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

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

LZSS, длина словаря — [math]8[/math] байт (символов). Коды сжатого сообщения — Кодисходного сообщения png.png

773105d8ce08592398f078963ff920ff.png

Практическое использование алгоритма LZSS

Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода (Алгоритм Хаффмана, алгоритм Шеннона-Фано (Shannon-Fano)) например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в ARJ — LZSS с алгоритмом Хаффмана.

См.также

Источники информации

  • Д.Сэломон. Сжатие данных, изображений и звука - Москва: Техносфера, 2004. - с.368, стр. 88.
  • Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. – 115 с., стр.60-62.
  • Лидовский В.В. Теория информации: учебное пособие. – Москва: 2003. – 112 с., с. 37-38.