Изменения

Перейти к: навигация, поиск

Алгоритм LZSS

7 байт добавлено, 22:07, 2 ноября 2014
Нет описания правки
== Оптимизации==
LZSS, помимо окна с содержимым сообщения, поддерживает двоичное дерево для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в дерево поиска, а подстрока, покидающая словарь, удаляется из дерева. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина> . Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения.
Алгоритм последовательно выполняет следующие действия:
1. кодирует содержимое буфера;
2. считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
3. вставляет в дерево новые строки, соответствующие считанным символам.
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, длина>. Если это символ, то следующие <math>8 битов </math> бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
===Пример декодирования===
142
правки

Навигация