Изменения
→Оптимизации
== Оптимизации==
Быстродействие и кодера, и декодера зависит от того, как реализовано “скольжение” "скольжение" окна по содержимому сообщения. В LZSS для работы с окном используется циклический буфер, организованный на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Это дает очень существенный выигрыш потому, что отсутствует постоянное сдвигание большого блока памяти. Если размер циклического буфера равен степени двойки, то стандартная для циклического буфера операция “смещение "смещение по модулю размер”размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
Быстродействие кодера [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. Если искать совпадение полным перебором всех возможных вариантов, то очевидно, что сжатие будет очень медленным. Поэтому в LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу (как внутреннему, так и листовому) соответствует определенная строка словаря длины <math>M</math> (максимальная длина совпадения). Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк.
