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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Оптимизации)
м (Организация поиска в словаре)
 
(не показано 60 промежуточных версий 3 участников)
Строка 1: Строка 1:
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:буфер, содержащий еще не закодированные символы, сохранялся в циклической [[Очередь|очереди]], буфер поиска (словарь) хранился в виде [http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 двоичного дерева поиска] и метки имели два поля, а не три.
+
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
 +
*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]]
 +
*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]]
 +
*метки имеют два поля, а не три
  
 +
== Модель данных ==
  
== Оптимизации==
+
===Реализация "скольжения"===
В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу (как внутреннему, так и листовому) соответствует  определенная строка словаря длины М (максимальная длина совпадения). Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк.
+
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
 
  
Проблема отсутствия совпадений в словаре решается путем введения дополнительного служебного бита (со значением «0» для незакодированных символов и «1» для кодовых комбинаций) , значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении.
+
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
  
== Модель данных ==
+
===Организация поиска в словаре===
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого
 
идентичен размеру скользящего окна. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть
 
окна автоматически означает удаление идентичной по длине порции из его задней части. Размер окна кратен степени двойки.
 
  
Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк. Покажем на примере, как двоичное дерево способно ускорить поиск в словаре.
+
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части размером длины буфера.  
===Пример===
+
====Порядок изменения дерева поиска====
 +
Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
 +
На дереве все время находится одинаковое число <tex>T </tex> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <tex>T=S-L+1</tex>.
  
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера. После ввода первых <math>16+5</math>   символов скользящее окно выглядит так:
+
Если во время кодирования  случается совпадение длины <tex>k</tex>, то дерево надо перестроить путем удаления <tex>k</tex> строк и добавления <tex>k</tex> строк.
  
{| border="1"                          
+
Удаляться будут первые  <tex>k</tex> строк буфера поиска до его сдвига, а добавляться будут последние  <tex>k</tex> строк этого буфера после сдвига.
 +
 
 +
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <tex>L</tex>  символов буфера поиска и добавить ее на дерево. Это следует повторить  <tex>k</tex> раз.
 +
 
 +
Для  определения смещения уславливаемся, что:
 +
*  нулевое смещение зарезервировали для обозначения конца кодирования;
 +
* если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.
 +
 
 +
 
 +
Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.
 +
 
 +
====Пример====
 +
Пусть входной файл содержит следующую последовательность: "sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из <tex>16</tex>-байтного буфера поиска и <tex>5</tex>-байтного буфера, содержащего еще не закодированные символы. После ввода первых <tex>16+5</tex>  символов скользящее окно выглядит так:
 +
 
 +
{| class="wikitable"                        
 
  |style="background:#FFCC00" |sid_eastman_clum  
 
  |style="background:#FFCC00" |sid_eastman_clum  
 
  |style="background:#FFCC00"|sily_
 
  |style="background:#FFCC00"|sily_
Строка 27: Строка 43:
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
  
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.) (их двенадцать, так как <math>12=16-5+1</math> ), которые помещены на двоичное дерево поиска вместе с их смещениями.
+
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
На дереве все время находится одинаковое число T узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число T равно: длина буфера поиска минус длина буфера,содержащего еще не закодированные символы, плюс 1 <math>(T=S-L+1)</math>.
 
  
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
+
'''Таблицы 1 и 2. Строки по пять символов.'''
(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <math>L-1</math> .)
+
{|
 
+
   |
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку (16,2). Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
+
{| class="wikitable"
 
+
! colspan="2" |Таблица 1
si 
 
{| border="1"
 
   |si                       
 
  |style="background:#FFCC00"|d_eastman_clumsi
 
  |style="background:#FFCC00"|ly_te_
 
  |ases_sea_sick_seals
 
|}
 
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины k , то дерево надо было бы перестроить путем удаления  k строк и добавления  k строк.
 
 
 
Удаляться будут первые  k строк буфера поиска до его сдвига, а добавляться будут последние  k строк этого буфера после сдвига.
 
 
 
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних 5 символов буфера поиска и добавить ее на дерево. Это следует повторить  k раз.
 
{| border="1"
 
 
  |-
 
  |-
 
  | sid_e
 
  | sid_e
Строка 85: Строка 87:
 
  |05
 
  |05
 
  |}
 
  |}
 +
  | ||
 +
  |
 +
{| class="wikitable"
 +
! colspan="2" |Таблица 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. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
 +
Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <tex>L-1</tex>.
 +
 
 +
В нашем примере длина совпадения равна <tex>2</tex>, поэтому кодер выдает метку <tex>\langle</tex><tex>16,2</tex><tex>\rangle</tex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
 +
 +
{| class="wikitable"
 +
  |si                       
 +
  |style="background:#FFCC00"|d_eastman_clumsi
 +
  |style="background:#FFCC00"|ly_te
 +
  |ases_sea_sick_seals
 +
|}
 +
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
 +
Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.
 +
В данном примере длина буфера {{---}} <tex>5</tex> символов, часть совпадения {{---}} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
 +
 
 +
===Оптимизация памяти===
 +
 
 +
У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ.  Такое кодирование существенно понижает производительность алгоритма.
 +
 
 +
Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением "0" для незакодированных символов и "1" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.
  
 
== Кодер LZSS ==
 
== Кодер LZSS ==
Строка 94: Строка 157:
 
Алгоритм последовательно выполняет следующие действия:
 
Алгоритм последовательно выполняет следующие действия:
  
# кодирует содержимое буфера;
+
# Кодирует содержимое буфера.
# считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
+
# Считывает очередные символы в буфер, удаляя при необходимости наиболее "старые" строки из словаря.
# вставляет в дерево новые строки, соответствующие считанным символам.
+
# Вставляет в дерево новые строки, соответствующие считанным символам.
 +
 
 
===Завершение работы===
 
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
+
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения.
 
 
===Добавление новой строки в дерево===
 
Вся работа по поиску расположения и установлению длины максимального совпадения содержимого словаря с буфером происходит в процессе добавления в дерево новой строки.
 
 
 
При добавлении строки в дерево алгоритм последовательно перемещается от корня дерева к его листу, каждый раз осуществляя лексикографическое сравнение новой строки и узла дерева. В зависимости от результата сравнения выбирается больший или меньший потомок этого узла и запоминается длина совпадения строк и положение текущего узла.
 
 
 
Если в результате сравнения оказывается, что содержимое буфера и строка, на которую ссылается текущий узел, в точности совпадают, то ссылки в текущем узле обновляются так, чтобы они указывали на буфер, и процедура добавления строки в дерево завершается.
 
 
 
Если потомок текущего узла, выбранный для очередного шага, отмечен как несуществующий, остается заполнить его соответствующей ссылкой и завершить работу.
 
 
 
Нужно отметить, что при окончании работы процедуре добавления строки известны и смещение, и длина наибольшего совпадения, и для этого не потребовался полный перебор всех возможных вариантов совпадения.
 
 
 
===Удаление строки из дерева===
 
При удалении узла из дерева возможны два варианта. Если узел имеет не более одного потомка, то удаление узла осуществляется простым исправлением ссылок “родитель-потомок”. Если узел имеет два потомка, то необходимы другие действия: найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего потомка и последующим перемещением от него по дереву до листа по большим ветвям.
 
  
 
===Пример кодирования===
 
===Пример кодирования===
 +
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
 +
В данном примере один символ кодируется восемью битами. Поэтому после префикса <tex>0</tex> декодер считывает следующие <tex>8</tex> бит.
 +
После префикса <tex>1</tex> хранится пара  <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex>. Так как смещение и длина не превосходят длины словаря, то размер пары <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex> равен удвоенному количеству бит, требуемых для хранения длины словаря.
 +
Длина словаря в данном примере <tex>8</tex>. Поэтому после префикса <tex>1</tex> декодер считывает <tex>6</tex> бит.
  
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
 
  
 
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png‎]]
 
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png‎]]
 +
 
==Декодер LZSS==
 
==Декодер LZSS==
  
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
  
Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, длина>. Если это символ, то следующие <math>8</math> бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
+
Декодер читает один бит сжатой информации и решает — это символ или пара <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex>. Если это символ, то следующие <tex>8</tex> бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
  
 
===Пример декодирования===
 
===Пример декодирования===
  
LZSS, длина словаря — 8 байт (символов). Коды сжатого сообщения —
+
LZSS, длина словаря — <tex>8</tex> байт (символов). Коды сжатого сообщения —
 
[[Файл:Кодисходного_сообщения_png.png‎ ]]  
 
[[Файл:Кодисходного_сообщения_png.png‎ ]]  
  
Строка 137: Строка 191:
 
например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в  
 
например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в  
 
ARJ —  LZSS с [[Алгоритм Хаффмана|алгоритмом Хаффмана]].
 
ARJ —  LZSS с [[Алгоритм Хаффмана|алгоритмом Хаффмана]].
 +
 +
== См.также ==
 +
* [[Алгоритмы LZ77 и LZ78]]
 +
* [[Алгоритм LZW]]
  
 
== Источники информации ==
 
== Источники информации ==
Строка 149: Строка 207:
 
*[http://www.intuit.ru/studies/courses/2256/140/lecture/3914?page=1/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
 
*[http://www.intuit.ru/studies/courses/2256/140/lecture/3914?page=1/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
  
== См.также ==
 
* [[Алгоритмы LZ77 и LZ78]]
 
* [[Алгоритм LZW]]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Алгоритмы сжатия ]]
 
[[Категория: Алгоритмы сжатия ]]

Текущая версия на 22:26, 15 ноября 2014

Эта версия алгоритма 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.