Редактирование: LZSS

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Алгоритмы сжатия ]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)