Для сжатия данных используют как статистические, так и эвристические
алгоритмы. Статистические алгоритмы для своей работы требуют знания
вероятностей появления символов в тексте. Как правило, эти вероятности
неизвестны. Для их оценки используют частоты символов. Однако, при
однопроходной обработке файла, эти частоты также неизвестны. Поэтому все
статистические алгоритмы можно поделить на три класса:
* неадаптивные - используют фиксированые, наперед заданые вероятности
символов. Таблица вероятностей символов не передается вместе с файлом, т.к.
она заранее известна. Недостаток: узкий класс файлов для которых достигается
приемлемый уровень сжатия.
* полуадаптивные - для каждого файла строят таблицу частот символов и с ее
помощью сжимают файл. Вместе с сжатым файлом передается таблица символов.
Такие алгоритмы достаточно хорошо сжимают большинство файлов, но требуется
дополнительная передача таблицы частот символов.
* адаптивные - начинают работать с фиксированной начальной таблицей частот
символов (обычно все символы изначально одинаково вероятны) и в процессе
работы это таблица изменяется в зависимости от встречаемых символов файла.
Преимущества: однопроходность алгоритма; также как и неадаптивные алгоритмы,
не требуется передача таблицы частот символов, но достаточно эффективно
сжимается широкий класс файлов.
Эвристические алгоритмы сжатия (типа 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
Обозначения: Ниже приводятся значения различных количеств информации для файлов различных типов. Наиболее удобны для практической реализации варианты 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
M 2
SUM log ( Pi/Qi )
i=1
При выборе языка и кодировки, имеющих наименьшее значение количества
информации, вычисленного по этой формуле, достигалась наименьшая
ошибка в определении языка и кодировки по частоте наиболее часто
встречающихся N-грамм (N <= 5).
| Изменена 19.03.2011 06:45 MSK |
|
|