Изменения

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

Алгоритм LZSS

795 байт добавлено, 19:28, 3 ноября 2014
Нет описания правки
== Оптимизации==
В LZSS помимо окна с содержимым сообщения поддерживает двоичное при кодировании поддерживается бинарное лексикографически упорядоченное дерево для ускорения поиска , в котором каждому узлу (как внутреннему, так и листовому) соответствует определенная строка словаря длины М (максимальная длина совпадения). Каждая подстрокаПоиск осуществляется путем последовательного сравнения кодируемой строки со строками, покидающая буферсоответствующими узлам дерева, добавляется в проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска, а подстрока, покидающая буфер поиска, удаляется из дереватрансформируется. Трансформация производится посредством удаления и добавления строк. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Проблема отсутствия совпадений в словаре решается путем введения дополнительного служебного бита, значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении.
142
правки

Навигация