142
правки
Изменения
LZSS
,Новая страница: «Эта версия алгоритма LZ77 была разработана Сторером (''Storer'') и Сжиманск...»
Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям: упреждающий буфер сохранялся в циклической очереди, буфер поиска (словарь) хранился в виде дерева двоичного поиска и метки имели два поля, а не три.
== Оптимизации==
LZSS, помимо окна с содержимым сообщения, поддерживает двоичное дерево для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в дерево поиска, а подстрока, покидающая словарь, удаляется из дерева. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения.
== Модель данных ==
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения доступ к нему организован как к кольцевому, и размер окна кратен степени 2.
Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
== Кодер LZSS ==
===Инициализация===
Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.
===Основной цикл работы===
Алгоритм последовательно выполняет следующие действия:
1. кодирует содержимое буфера;
2. считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
3. вставляет в дерево новые строки, соответствующие считанным символам.
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
===Пример кодирования===
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png]]
==Декодер LZSS==
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, длина>. Если это символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
===Пример декодирования===
LZSS, длина словаря - 8 байт (символов). Коды сжатого сообщения -
[[Файл:Кодисходного_сообщения_png.png ]]
[[Файл:773105d8ce08592398f078963ff920ff.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]
*[http://www.intuit.ru/studies/courses/2256/140/lecture/3914?page=1/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
== Оптимизации==
LZSS, помимо окна с содержимым сообщения, поддерживает двоичное дерево для ускорения поиска совпадения. Каждая подстрока, покидающая буфер, добавляется в дерево поиска, а подстрока, покидающая словарь, удаляется из дерева. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Кодер LZSS использует однобитовый префикс, для того чтобы отличать незакодированные символы от пар <смещение, длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщения.
== Модель данных ==
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения доступ к нему организован как к кольцевому, и размер окна кратен степени 2.
Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
== Кодер LZSS ==
===Инициализация===
Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.
===Основной цикл работы===
Алгоритм последовательно выполняет следующие действия:
1. кодирует содержимое буфера;
2. считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
3. вставляет в дерево новые строки, соответствующие считанным символам.
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
===Пример кодирования===
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png]]
==Декодер LZSS==
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, длина>. Если это символ, то следующие 8 битов выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
===Пример декодирования===
LZSS, длина словаря - 8 байт (символов). Коды сжатого сообщения -
[[Файл:Кодисходного_сообщения_png.png ]]
[[Файл:773105d8ce08592398f078963ff920ff.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]
*[http://www.intuit.ru/studies/courses/2256/140/lecture/3914?page=1/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия ]]
