Алгоритм LZSS

Алгоритм LZSS

     Этот  алгоритм получил свое название по именам своих  разработчиков: Lempel, Ziv, Storer, Szimansky. Существенный вклад в развитие алгоритма внес Т. С. Bell.

     LZSS является развитием LZ77 и стремится избавиться от недостатков своего предшественника. LZSS отличается от LZ77 тем, как поддерживается скользящее окно и какие коды выдает компрессор.

     LZSS, помимо собственно окна с содержимым  сообщения, поддерживает хеш-таблицу для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в хеш-таблицу поиска, а подстрока, покидающая словарь, удаляется из хеш-таблицы. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от LZ77, становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя в скорости сжатия.

     Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения. 

     Пример  работы алгоритма

     Наш входной буфер "1231231", в двоичном это 56 бит:

     00000001 00000010 00000011 00000001 00000010 00000011 00000001

            1               2               3               1               2               3               1       

     Подчеркивание символа указывает текущую позицию.

     Начало  кодирования. 
 
 
Входные данные = "1231231" 
- Мы начинаем с первого байта "1". Мы видели его раньше? Кодировать как литерал. 
 
Выходные данные = 0 00000001 
 
Входные данные = "1231231" 
- Следующий байт "2". Мы видели его раньше? Кодировать как литерал. 
 
Выходные данные = 0 00000001 0 00000010 
 
 
Входные данные = "1231231" 
- Следующий байт "3". Мы видели его раньше? Кодировать как литерал. 
 
Выходные данные = 0 00000001 0 00000010 0 00000011 
 
 
Входные данные = "1231231" 
- Следующий байт "1". Мы видели его раньше? Да. Когда? 3 байта назад. Какое количество байт в совпадении? 3 байта совпадения "123". Выходной флаг "1" (1 бит) с последующим смещением "3" (4 бита) и длиной «3» (3 бита). Затем пропустить 3 байта данных. 
 
Выходные данные = 0 00000001 0 00000010 0 00000011 1 0011 011 
 
Входные данные = "1231231" 
- Следующий байт "1". Разве мы видели это раньше? Да. Когда? 3 байта назад. Какое количество байт в совпадении? 1 байта совпадения "1". Выходной флаг "1" (1 бит) с последующим смещением "3" (4 бита) и длиной «1» (3 бита). 
 
Выходные данные = 0 00000001 0 00000010 0 00000011 1 0011 011 1 0011 001 

     Итак, исходные данные составляла 56 бит, и выходные данные составляет 43 бит. Не плохо для такого небольшого количества данных. 

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

     Как и в LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности “скольжения” окна по содержимому сообщения доступ к нему организован как к кольцевому, и размер окна кратен степени 2.

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

Кодер LZSS

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

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

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

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

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

     Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в заголовок сжатого файла LZSS ID (4 байта) и несжатый размер (4 байта).

Работа хеш-таблицы.

     Вся работа по поиску расположения и установлению длины максимального совпадения содержимого словаря с буфером происходит в процессе добавления в хеш-таблицу новой записи.

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

     При добавлении элементов в хеш-таблицу  выделяются куски динамической памяти, которые организуются в виде связанных  списков, каждый из которых соответствует  входу хеш-таблицы.

Декодер LZSS

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

     Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, дли-на>. Если это символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде.