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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример)
м (Организация поиска в словаре)
 
(не показано 19 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
 
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям:
 
*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]]
 
*буфер, содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]]
*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]];
+
*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]]
*метки имеют два поля, а не три.
+
*метки имеют два поля, а не три
  
 
== Модель данных ==  
 
== Модель данных ==  
  
 
===Реализация "скольжения"===
 
===Реализация "скольжения"===
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]],в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
+
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77.  Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
  
Размер циклического буфера равен степени двойки и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.  
+
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
  
 
===Организация поиска в словаре===
 
===Организация поиска в словаре===
  
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <math>M</math> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части, размером длины буфера.  
+
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом  осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует  определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве  хранятся все подстроки словарной части размером длины буфера.  
 
====Порядок изменения дерева поиска====
 
====Порядок изменения дерева поиска====
Кодер изучает буфер поиска, создавая  <math>T </math> строк с числом символов  <math>L</math> , которые помещены на двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
+
Кодер изучает буфер поиска, создавая  <tex>T </tex> строк с числом символов  <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <math>T=S-L+1</math>.
+
На дереве все время находится одинаковое число <tex>T </tex> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <tex>T=S-L+1</tex>.
  
Если во время кодирования  случается совпадение длины <math>k</math>, то дерево надо перестроить путем удаления <math>k</math> строк и добавления <math>k</math>  строк.
+
Если во время кодирования  случается совпадение длины <tex>k</tex>, то дерево надо перестроить путем удаления <tex>k</tex> строк и добавления <tex>k</tex>  строк.
  
Удаляться будут первые  <math>k</math> строк буфера поиска до его сдвига, а добавляться будут последние  <math>k</math> строк этого буфера после сдвига.
+
Удаляться будут первые  <tex>k</tex> строк буфера поиска до его сдвига, а добавляться будут последние  <tex>k</tex> строк этого буфера после сдвига.
  
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <math>L</math>  символов буфера поиска и добавить ее на дерево. Это следует повторить  <math>k</math> раз.
+
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <tex>L</tex>  символов буфера поиска и добавить ее на дерево. Это следует повторить  <tex>k</tex> раз.
  
 
Для  определения смещения уславливаемся, что:
 
Для  определения смещения уславливаемся, что:
Строка 32: Строка 32:
  
 
====Пример====
 
====Пример====
Пусть входной файл содержит следующую последовательность: «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"                           
Строка 43: Строка 43:
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
 
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
  
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <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
Строка 88: Строка 90:
 
   |
 
   |
 
{| class="wikitable"
 
{| class="wikitable"
 +
! colspan="2" |Таблица 2
 
  |-
 
  |-
 
  |d_eas
 
  |d_eas
Строка 127: Строка 130:
 
|}
 
|}
  
 +
Первым символом в буфере, содержащем еще не закодированные символы, является 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><math>16,2</math><math>\rangle</math>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
 
 
   
 
   
 
{| class="wikitable"
 
{| class="wikitable"
Строка 143: Строка 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>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
  
 
===Оптимизация памяти===
 
===Оптимизация памяти===
Строка 148: Строка 149:
 
У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ.  Такое кодирование существенно понижает производительность алгоритма.
 
У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ.  Такое кодирование существенно понижает производительность алгоритма.
  
Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением «0» для незакодированных символов и «1» для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.
+
Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением "0" для незакодированных символов и "1" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.
 
 
  
 
== Кодер LZSS ==
 
== Кодер LZSS ==
Строка 158: Строка 158:
  
 
# Кодирует содержимое буфера.
 
# Кодирует содержимое буфера.
# Считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря.
+
# Считывает очередные символы в буфер, удаляя при необходимости наиболее "старые" строки из словаря.
 
# Вставляет в дерево новые строки, соответствующие считанным символам.
 
# Вставляет в дерево новые строки, соответствующие считанным символам.
  
 
===Завершение работы===
 
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
+
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения.
  
 
===Пример кодирования===
 
===Пример кодирования===
 
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
 
Закодировать по алгоритму 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> бит.
 +
 
  
 
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png‎]]
 
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png‎]]
Строка 174: Строка 177:
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
 
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
  
Декодер читает один бит сжатой информации и решает — это символ или пара <math>\langle</math><math>offset,length</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‎ ]]  
  

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