Методы сжатия на пальцах


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Методы сжатия на пальцах

Главный критерий того, понимаете ли вы что-нибудь в методах сжатия - наличие ответа на вопрос - как Вы лично будете реализовывать алгоритм сжатия для того или иного случая.

Итак, как Вы будете писать сжимающий алгоритм?

Ну, вот тут если несколько ноликов подряд, мы заменим их на количество и один нолик...

Немедленно бросьте это ламерство! Давайте рассмотрим более серьезные подходы!

Алгоритм сжатия состоит их двух компонент - моделирования и кодирования.
Иначе говоря, есть задача как можно более точного предсказания того, что встретится дальше во входном потоке и есть задача оптимального кодирования на основании этого знания.

Кодирование

Вот как раз насчет кодирования бояться не надо. Методов кодирования полным-полно и все они давно исхожены вдоль и поперек. Самый точный - арифметическое кодирование. Говорят, оно медленное.

Да не такое уж и медленное. Но если Вам мало 100кБайт/с, то используйте Хаффмана...

С крайнем случае, есть еще всякие квазиарифметические кодинги, Range кодинг, Шеннон-Фоно, Rice кодинг, да мало ли чего...

Главное, что Вам надо разучить сочиняя алгорим - сперва надо собрать его с Арифметическим кодингом и оценить степень сжатия. Потом, если степень сжатия достаточно высока (1-2% потерять не жалко), а быстродействия не хватает, можно попытаться заменить арифметику на что-нибудь другое. Что касается меня, я ее ни на что не променяю - меня за байт жаба насмерть задушит. Что касается быстродействия - ну и пусть себе тормозит :)

Моделирование

А вот моделей - видимо-невидимо. Ладно, рассмотрим основные.

Словарные модели

Лемпел и Зив в 1977 году придумали. Раз слово в тексте встретилось, значит, возможно, скоро еще раз встретится. Не слово - так часть слова. А то и целая фраза. А мы ее закодируем как расстояние до нее и длину. Это LZ77, LZSS и все, что называется словарными алгоритмами со скользящим окном.

Как это реализуется на практике? Чтоб красиво?

Какой длины может встретиться фраза? Ну, например, 70 символов, больше - маловероятно. Причем длины до 4 мы игнорируем - нечего с ними возиться!

Мы говорим арифметическому кодеру, что у нас не 256 символов во входном алфавите, а 256+70-4=322. Ок. Теперь если у нас подстрока раньше не встречалась, мы ее просто кидаем посимвольно в арифметический кодер. Если нашлась, то мы вычисляем длину совпадения и расстояние до него. От длины вычитаем 4, добавляем 256 и кидаем в арифметический кодер. И следом кидаем расстояние. Расстояние может быть, скажем, 0..8191 для 8 килобайтного окна/словаря (называйте как хотите). Кодируйте его опять-таки как хотите.

Арифметический декодер раскодирует символ. Если он меньше 256 - это просто символ, если больше - он вычитает 256, прибавляет 4 (получает число от 4 до 70 - это длина), лезет в арифметический декодер за расстоянием, затем лезет в уже раскодированный поток символов, смещается на это самое расстояние, достает это самое количество символов и копирует в входной поток.

Я рад если Вам понятно.

Можно сделать и по-другому, можно, к примеру, перед невстречавшейся группой символов поставить какой-нибудь код и длину группы и гнать их 1:1.

Как лучше? На пальцах: лучше там, где выше степень сжатия.

По научному. Лучше там, где точнее предсказывается вероятность. Какова вероятность того, что такая-то подстрока встретится еще раз? Вот с такой вероятностью это и надо кодировать. Оптимально чтобы. Не понятно как это все оценить? Мне тоже не всегда все понятно. Потому я и взялся объяснять на пальцах.

Ок. Вторая группа словарных методов. LZ78 - LZW - LZFH - RFGD.

Эти методы имеют не буфер, а настоящий словарь. Символы запихиваются в двоичные деревья.

Подстроки соответствуют вершинам деревьев. Кодирование никакое не используется - в выходной поток просто гонятся номера вершин, соответствующих встретившимся подстрокам. Долго рассказывать Интересно - почитайте, про LZW сказок полно.

Статистические методы.

Есть понятие порядка метода. Метод порядка 0 - ему вообще ничего не интересно. Метод порядка 1 - анализирует один предшествующий символ. Порядка 2 - анализирует 2 символа. И так далее. Всякие арифметические кодеры и Хаффманы сами по себе являются статистическими методами нулевого порядка. И есть такая вещь - контекст. Метод порядка 0 использует контекст порядка 0. Метод порядка 4 использует контексты порядка с -1 (где вообще все символы равновероятны) по 4. Что же такое контекст? Это такая ерунда, которая содержит информацию о том, с какой вероятностью какой символ встретится. И вот у нас есть 1 контекст 0-го порядка, 256 контекстов 1-го порядка (для каждого предшествующего символа - по 1), 65536 контекстов 2-го порядка (это столько бывает пар символов) и т.д. Чтобы экономить память, физически в алгоритме создают не все контексты, а только те, которые нужны.

И вот оценивают вероятность следующего символа в контекстах разных порядков. Умножают на веса контекстов и складывают. И по результату кодируют. Получается гораздо лучше, чем при любом словарном методе. Не верите - сравните архиватор HA с ключами А1 и А2.

Как вычислять веса контекстов? Да просто смотри какой из контекстов лучше предсказывает, ему и вес побольше! Это был метод перемешивания.

Есть еще метод исключений. Он не такой точный, зато попроще и побыстрей. Пытаются закодировать символ в контексте максимальной длины. Если его там нет (он в этом контексте не встречался), то кодируется вероятность ухода, пытаемся кодировать символ в контексте меньшего порядка и т.д. до порядка -1 - уж там-то он точно закодируется. Если символ вдруг в контексте есть, то мы его там и кодируем и контексты меньших порядков вообще не рассматриваем - сразу переходим к следующему символу.

Есть еще всякая экзотика. Борл-Веллер трансформ, например. Жмет текст почти так же, как лучшие статистические методы. Работает так. Делает над текстом хитрое преобразование, "тусующее" буквы. После него буквы сильно группируются, т.е. получаются большие серии из одинаковых букв, стоящих подряд. Ну, а уж их-то закодировать как-нибудь можно :)...

Константин Балашев
http://cotty.16x16.com

Методы сжатия на пальцах

Кодирование

Моделирование

Словарные модели

Статистические методы.

Константин Балашев http://cotty.16x16.com

Константин Балашев
http://cotty.16x16.com