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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавление новой строки в дерево)
м (rollbackEdits.php mass rollback)
 
(не показаны 42 промежуточные версии 4 участников)
Строка 1: Строка 1:
 
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
 
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]];
+
*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]]
*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]];
+
*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]]
*метки имеют два поля, а не три.
+
*метки имеют два поля, а не три
  
 +
== Модель данных ==
  
== Оптимизации==
+
===Реализация "скольжения"===
 +
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
  
Быстродействие и кодера, и декодера зависит от того, как реализовано "скольжение" окна по содержимому сообщения. В LZSS для работы с окном используется циклический буфер, организованный на физически сплошном участке памяти, а не  на реальном сдвиге содержимого окна, как в LZ77.  Это дает очень существенный выигрыш потому, что отсутствует постоянное сдвигание большого блока памяти. Если размер циклического буфера равен степени двойки, то стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
+
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
  
Быстродействие кодера [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. Если искать совпадение полным перебором всех возможных вариантов, то очевидно, что сжатие будет очень медленным. Поэтому в LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу (как внутреннему, так и листовому) соответствует  определенная строка словаря длины <math>M</math> (максимальная длина совпадения). Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк.
+
===Организация поиска в словаре===
Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
 
  
У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4 Кб, а буфер — 16 байтов, то код<math>\langle</math> 0, 0, символ<math>\rangle</math> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением «0» для незакодированных символов и «1» для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.
+
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части размером длины буфера.
 +
====Порядок изменения дерева поиска====
 +
Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
 +
На дереве все время находится одинаковое число <tex>T </tex> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <tex>T=S-L+1</tex>.
  
== Модель данных ==
+
Если во время кодирования  случается совпадение длины <tex>k</tex>, то дерево надо перестроить путем удаления <tex>k</tex> строк и добавления <tex>k</tex>  строк.
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого
 
идентичен размеру скользящего окна. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть
 
окна автоматически означает удаление идентичной по длине порции из его задней части. Размер окна кратен степени двойки.
 
  
Дерево поиска, как упоминалось выше, представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
+
Удаляться будут первые  <tex>k</tex> строк буфера поиска до его сдвига, а добавляться будут последние  <tex>k</tex> строк этого буфера после сдвига.
  
===Порядок изменения дерева поиска===
+
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <tex>L</tex>  символов буфера поиска и добавить ее на дерево. Это следует повторить  <tex>k</tex> раз.
Кодер изучает буфер поиска, создавая  <math>T </math> строк с числом символов  <math>L</math> , которые помещены на двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
 
На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число <math>T </math> равно: длина буфера поиска <math>S</math> минус длина буфера, содержащего еще не закодированные символы <math>L</math>, плюс 1 <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> раз.
 
  
 
Для  определения смещения уславливаемся, что:
 
Для  определения смещения уславливаемся, что:
 
*  нулевое смещение зарезервировали для обозначения конца кодирования;  
 
*  нулевое смещение зарезервировали для обозначения конца кодирования;  
* символ <math>S_t</math> соответствует единичному смещению относительно символа <math>S_t+_1</math> , с которого начинается буфер;
 
 
* если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.
 
* если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.
  
  
 
Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.
 
Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.
===Пример===
 
  
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного буфера, содержащего еще не закодированные символы. После ввода первых <math>16+5</math>  символов скользящее окно выглядит так:
+
====Пример====
 +
Пусть входной файл содержит следующую последовательность: "sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из <tex>16</tex>-байтного буфера поиска и <tex>5</tex>-байтного буфера, содержащего еще не закодированные символы. После ввода первых <tex>16+5</tex>  символов скользящее окно выглядит так:
  
 
{| class="wikitable"                           
 
{| class="wikitable"                           
Строка 51: Строка 43:
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
  
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.) (их двенадцать, так как <math>12=16-5+1</math> ), которые помещены на двоичное дерево поиска вместе с их смещениями.
+
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
 +
 
 +
'''Таблицы 1 и 2. Строки по пять символов.'''
 +
{|
 +
  |
 
{| class="wikitable"
 
{| class="wikitable"
 +
! colspan="2" |Таблица 1
 
  |-
 
  |-
 
  | sid_e
 
  | sid_e
Строка 90: Строка 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>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
 
 
 
 
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
 
(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <math>L-1</math> .)
 
 
 
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку <math>\langle</math>16,2<math>\rangle</math>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
 
 
   
 
   
 
{| class="wikitable"
 
{| class="wikitable"
 
   |si                         
 
   |si                         
 
   |style="background:#FFCC00"|d_eastman_clumsi
 
   |style="background:#FFCC00"|d_eastman_clumsi
   |style="background:#FFCC00"|ly_te_
+
   |style="background:#FFCC00"|ly_te
 
   |ases_sea_sick_seals
 
   |ases_sea_sick_seals
 
  |}
 
  |}
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi.
+
С дерева необходимо удалить строки 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 ==
Строка 115: Строка 158:
  
 
# Кодирует содержимое буфера.
 
# Кодирует содержимое буфера.
# Считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря.
+
# Считывает очередные символы в буфер, удаляя при необходимости наиболее "старые" строки из словаря.
 
# Вставляет в дерево новые строки, соответствующие считанным символам.
 
# Вставляет в дерево новые строки, соответствующие считанным символам.
  
 
===Завершение работы===
 
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
+
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения.
 
 
===Удаление строки из дерева===
 
При удалении узла из дерева возможны два варианта. Если узел имеет не более одного потомка, то удаление узла осуществляется простым исправлением ссылок “родитель-потомок”. Если узел имеет два потомка, то необходимы другие действия: найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего потомка и последующим перемещением от него по дереву до листа по большим ветвям.
 
  
 
===Пример кодирования===
 
===Пример кодирования===
 +
Закодировать по алгоритму 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‎]]
Строка 135: Строка 177:
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
  
Декодер читает один бит сжатой информации и решает — это символ или пара <math>\langle</math>смещение, длина<math>\rangle</math>. Если это символ, то следующие <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‎ ]]  
  

Текущая версия на 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.