Сайт о сжатии  >>  ARCTEST

Сравнительные тесты
    Текстовые файлы
    Текстовые файлы (Mac)
    EXE-файлы
    EXE-файлы (Mac)
    Исполнимые EXE-сжатые
    Аудио: Wav-файлы
    Аудио: Wav-файлы (Mac)
    Графика: TIFF-файлы
    Графика: TIFF-файлы (Mac)
    Разноформатные файлы
    Разноформатные файлы (Mac)
    Файлы демо-игры
    Файлы демо-игры (Mac)
Альтернативные тесты
    Русский текст
    Английский текст
    Исходники
    WinWord-файл
    Excel-файл
    EXE-файл
    Новые тесты
Графические тесты
    Сжатие изображений без потерь
Новости
    Архив новостей
    Архив рассылки
Утилиты
    Просмотра-распаковки
    Идентификации-распаковки
    COM/EXE-распаковки, анализа
    Распаковки инсталляций
    Создания SFX-архивов/инсталляций
    Конвертирования
    Починки архивов
    Поиска
    Универсальные оболочки
    Управления баннерами
    Управления файлами
    Резервного копирования
    Тестирования
    Разные
Файл-менеджеры
    Файл-менеджеры
    Арх.-модули для FAR
    Арх.-модули для Win. Commander
Описания
    Статьи, интервью
    Теория, алгоритмы
    Self-описания архиваторов
    FAQ
    Разное
Линки
    Архиваторные
    COM/EXE/DLL-пакеров
Necromancer's DN
    О программе
    Новости свежих версий
    Архив новостей
Поддержка
   
    Подписка на рассылку новостей
    Архиваторные опросы
    Об авторе
Все о сжатии / arctest. Авторский проект.
---------------------------------------------------------

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

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

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

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

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

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

Кодирование

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

Да не такое уж и медленное. Но если Вам мало 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
Последнее обновление: 12-May-2022

Сайт о сжатии  >>  ARCTEST  >>  Сравнительные тесты  |  Альтернативные тесты  |  Графические тесты  |  Новости  |  Утилиты  |  Файл'менеджеры  |  Описания  |  Линки  |  Necromancer's DN  |  Поддержка

Поиск:
Справка Детальный запрос

Сайт о сжатии >>
  Новинки | О сервере | Статистика

  Книга "Методы сжатия данных" >>
     Универсальные | Изображений | Видео

  Разделы >> Download (статьи+исходники) | Ссылки | Ru.compress | Arctest | Видео | Каталог ссылок | Форум
  Проекты >> Д.Ватолина | А.Ратушняка | М.Смирнова | В.Юкина | Е.Шелвина | А.Филинского | Д.Шкарина | С.Оснача

  Оставьте ваши замечания, предложения, мнения!
  О найденных ошибках пишите на compression_на_graphicon.ru
  © Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин и др., текст, состав., 2001-2003
    Project supported by Graphics & Media Lab

   ЭТОТ ДОКУМЕНТ МОЖНО СКАЧАТЬ C http://www.compression.ru/compression.ru/arctest/descript/finger-comp.htm

Rambler's Top100 Рейтинг@Mail.ru