Изменения

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

Алгоритм LZSS

906 байт убрано, 10:52, 7 ноября 2014
→‎Оптимизации
*метки имеют два поля, а не три
== Оптимизации==
Быстродействие кодера и декодера зависит от того, как реализовано "скольжение" окна по содержимому сообщения. В LZSS для работы с окном используется циклический буфер, организованный на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Если размер циклического буфера равен степени двойки, то стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <math>M</math> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/40714»

Навигация