|
|
| Строка 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/ Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива]
| |
| − |
| |
| − | [[Категория: Дискретная математика и алгоритмы]]
| |
| − |
| |
| − | [[Категория: Алгоритмы сжатия ]]
| |
