Изменения

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

Алгоритм LZSS

5 байт добавлено, 22:24, 2 ноября 2014
Нет описания правки
LZSS помимо окна с содержимым сообщения поддерживает двоичное дерево для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в дерево поиска, а подстрока, покидающая словарь, удаляется из дерева. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина> . Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения.
== Модель данных ==
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения доступ к нему организован как к кольцевому, и размер окна кратен степени двойки.
Алгоритм последовательно выполняет следующие действия:
1. # кодирует содержимое буфера; 2. # считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря; 3. # вставляет в дерево новые строки, соответствующие считанным символам.
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
===Пример декодирования===
LZSS, длина словаря - 8 байт (символов). Коды сжатого сообщения -
[[Файл:Кодисходного_сообщения_png.png‎ ]]
==Практическое использование алгоритма LZSS==
Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода ([[Алгоритм Хаффмана]], алгоритм Шеннона-Фано(''Shannon-Fano''))
например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в
ARJ — LZSS с [[Алгоритм Хаффмана|алгоритмом Хаффмана]].
== Литература Источники информации ==
* Д.Сэломон. Сжатие данных, изображений и звука - Москва: Техносфера, 2004. - с.368, стр. 88.
* Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. – 115 с., стр.60-62.
==Ссылки==
*[http://mf.grsu.by/UchProc/livak/po/comprsite/theory_lzss.html/ Обзор алгоритмов сжатия без потерь. Алгоритм LZSS]
142
правки

Навигация