Сайт о сжатии >> ARCTEST
Сравнительные тесты Альтернативные тесты
Русский текст
Английский текст
Исходники
WinWord-файл
Excel-файл
EXE-файл
Новые тесты
|
|
Сжатие изображений без потерь
|
|
Архив новостей
|
|
Архив рассылки
|
|
Файл-менеджеры
Арх.-модули для FAR
Арх.-модули для Win. Commander
|
|
Статьи, интервью
Теория, алгоритмы
Self-описания архиваторов
FAQ
Разное
|
|
Архиваторные
COM/EXE/DLL-пакеров
|
|
О программе
Новости свежих версий
Архив новостей
|
Подписка на рассылку новостей
Архиваторные опросы
Об авторе
|
 |
 |
 |
|
[an error occurred while processing this directive]
|
||
 |
||
Суперадаптивное сжатие
Для сжатия данных используются как статистические, так и эвристические алгоритмы. Статистические алгоритмы (Хаффмана, Шеннона-Фано, арифметические) требуют знания вероятностей появления символов в тексте. Как правило, эти вероятности неизвестны. Для их оценки используют частоты символов. Однако, при однопроходной обработке файла, эти частоты также неизвестны. Поэтому все статистические алгоритмы можно разделить на три класса:
- Неадаптивные - используют фиксированные, заранее заданные вероятности символов. Таблица вероятностей символов не передается вместе с файлом, т.к. она заранее известна. Недостаток: узкий класс файлов, для которых достигается приемлемый уровень сжатия;
- Полуадаптивные - для каждого файла строят таблицу частот символов и с ее помощью сжимают файл. Вместе со сжатым файлом передается таблица символов. Такие алгоритмы достаточно хорошо сжимают большинство файлов, но требуется дополнительная передача таблицы частот символов;
- Адаптивные - начинают работать с фиксированной начальной таблицей частот символов (обычно все символы изначально одинаково вероятны) и в процессе работы это таблица изменяется в зависимости от встречаемых символов файла. Преимущества: однопроходность алгоритма; также как и неадаптивные алгоритмы, не требуется передача таблицы частот символов, но достаточно эффективно сжимается широкий класс файлов.
Эвристические алгоритмы сжатия (типа LZ77, LZ78), как правило, ищут повторяющиеся строки в файле, либо строят словарь как уже встречавшихся фраз, так и фраз, которые наиболее вероятно могут появится в тексте.
Обычно такие алгоритмы обладают целым рядом специфических параметров (размер буфера, максимальная длина фразы, размер рассматриваемого контекста и т.п.), подбор которых зависит от опыта автора алгоритма, и эти параметры подбираются так, чтобы добиться оптимального сочетания времени работы, коэффициента сжатия и широты класса хорошо сжимаемых файлов.
При подборе этих параметров можно заметить, что для различных файлов (текстовые, двоичные, базы данных) оптимальны различные сочетания параметров, не говоря уже о том, что разные алгоритмы оптимальны для разных классов исходных файлов.
Идея суперадаптивного сжатия заключается в адаптивности параметров сжимающего алгоритма, т.е. параметры алгоритма, или же сами алгоритмы сжатия, могут меняться в зависимости от текущего распределения частот символов в обрабатываемом файле. Алгоритм при этом остается однопроходным.
Вся тонкость заключается в решении о принадлежности данного файла к тому или иному классу. Можно заметить, что для файлов того или иного класса свойственно определенное распределение частот символов. Конечно, для каждого файла распределение частот уникально, но у файлов одного класса эти распределения не сильно различаются. Таким образом проблема сводится к определению вида распределения символов к которому ближе всего в данный момент распределение символов обрабатываемого файла.
Мерой близости одного распределения частот символов к другому может служить количество информации. В отличие от Шенноновской энтропии, существует несколько различных определений количества информации. Это связано с условиями, которые накладываются на нее. Этим условиям удовлетворяет несколько различных функций. Не вдаваясь в математические подробности, скажем самое главное: эта функция должна обращаться в ноль при равенстве распределений и положительной в других случаях.
Примерная схема суперадаптивного сжатия:
- Нам известны несколько различных алгоритмов сжатия и распределения частот для которых они оптимальны. Стартуем с фиксированного распределения частот и соответствующего ему алгоритма.
- Используя текущий алгоритм кодируем N очередных символов текста, изменяем таблицу частот встреченных символов, подсчитывает количество информации для всех известных распределений, определяем распределение к которому ближе всего текущее распределение символов (для него значение количества информации наименьшее), выбираем соответствующий ему алгоритм. И опять повторяем тоже самое для всего файла.
Различные варианты определения количества информации
Обозначим Pi и Qi частоты символов текста и частоты символов при которых оптимален некий алгоритм сжатия.
N N SUM Pi = SUM Qi = 1 i=1 i=1
Тогда количество информации можно определить следующими способами:
N
Kullback SUM Qi * log(Qi/Pi)
i=1
N
Kullback SUM Pi * log(Pi/Qi)
i=1
N
Kullback SUM (Qi-Pi) * log(Qi/Pi)
i=1
N 2
Matusita SQRT( SUM Pi * (SQRT(Qi/Pi)-1) )
i=1
1 N
Kolmogoroff - SUM Pi * ABS(Qi/Pi-1)
2 i=1
N
Bhattacharyya -log( SUM Pi * SQRT(Qi/Pi) )
i=1
N 2
Kagan SUM Pi * (1-Qi/Pi)
i=1
Обобщение N 2
наименьших квадратов SQRT( SUM Qi * (Pi/Qi) - 1 )
i=1
Обозначения: * - операция умножения;
log - логарифм по
основанию 2;
SUM - операция
суммирования;
SQRT - операция извлечения
квадратного корня;
ABS - модель числа;
Ниже приводятся значения различных количеств информации для файлов различных типов. Наиболее удобны для практической реализации варианты Kullbackа и Kaganа. Также приводится значение энтропии символа исследуемых файлов.
+++++ File: t.zip +++++
Shannon's Hentropy = 7.9980
Kullback's information gain = 0.0020
Kullback's reversed information gain = 0.0020
Kullback's divergency = 0.0040
Matusita information gain = 0.0262
Kolmogoroff's information gain = 0.0000
Bhattacharyya information gain = 0.0005
Kagan's information gain = 0.0027
MNS generalisation = 0.0527
+++++ File: DEFCAT.DB +++++
Shannon's Hentropy = 3.4174
Kullback's information gain = 4.5826
Kullback's reversed information gain = 2.3148
Kullback's divergency = 6.8974
Matusita information gain = 0.9575
Kolmogoroff's information gain = 0.3652
Bhattacharyya information gain = 0.8847
Kagan's information gain = 88.4309
MNS generalisation = 2.2684
+++++ File: FILELIST.DOC +++++
Shannon's Hentropy = 4.7476
Kullback's information gain = 3.2524
Kullback's reversed information gain = 0.2492
Kullback's divergency = 3.5016
Matusita information gain = 0.7056
Kolmogoroff's information gain = 0.3633
Bhattacharyya information gain = 1.2889
Kagan's information gain = 20.1490
MNS generalisation = 2.8623
+++++ File: l12.prt +++++
Shannon's Hentropy = 5.0039
Kullback's information gain = 2.9961
Kullback's reversed information gain = 1.2768
Kullback's divergency = 4.2729
Matusita information gain = 0.7841
Kolmogoroff's information gain = 0.3398
Bhattacharyya information gain = 1.0078
Kagan's information gain = 17.1672
MNS generalisation = 3.4860
+++++ File: sources.c +++++
Shannon's Hentropy = 5.6431
Kullback's information gain = 2.3569
Kullback's reversed information gain = 0.4507
Kullback's divergency = 2.8076
Matusita information gain = 0.6489
Kolmogoroff's information gain = 0.2871
Bhattacharyya information gain = 0.8291
Kagan's information gain = 10.1830
MNS generalisation = 1.5086
+++++ File: hi.exe +++++
Shannon's Hentropy = 6.6845
Kullback's information gain = 1.3155
Kullback's reversed information gain = 0.9956
Kullback's divergency = 2.3111
Matusita information gain = 0.5948
Kolmogoroff's information gain = 0.1777
Bhattacharyya information gain = 0.2808
Kagan's information gain = 7.8968
MNS generalisation = 1.5113
DEFCAT.DB - база данных Paradox FILELIST.DOC - список файлов пакета BC++ 3.1 (engl.) l12.prt - форматированный текст на русском языке.
Максим Захаров
Сайт о сжатии
>>
ARCTEST
>>
Сравнительные тесты
|
Альтернативные тесты
|
Графические тесты
|
Новости
|
Утилиты
|
Файл'менеджеры
|
Описания
|
Линки
|
Necromancer's DN
|
Поддержка
|
|
[an error occurred while processing this directive]
