LZSS — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Практическое использование алгоритма LZSS)
м (rollbackEdits.php mass rollback)
 
(не показаны 2 промежуточные версии 2 участников)
Строка 1: Строка 1:
Эта версия [[Алгоритмы 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/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Алгоритмы сжатия ]]
 

Текущая версия на 19:37, 4 сентября 2022