Суперадаптивное сжатие


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

Суперадаптивное сжатие

Для сжатия данных используются как статистические, так и эвристические алгоритмы. Статистические алгоритмы (Хаффмана, Шеннона-Фано, арифметические) требуют знания вероятностей появления символов в тексте. Как правило, эти вероятности неизвестны. Для их оценки используют частоты символов. Однако, при однопроходной обработке файла, эти частоты также неизвестны. Поэтому все статистические алгоритмы можно разделить на три класса:

Неадаптивные - используют фиксированные, заранее заданные вероятности символов. Таблица вероятностей символов не передается вместе с файлом, т.к. она заранее известна. Недостаток: узкий класс файлов, для которых достигается приемлемый уровень сжатия;
Полуадаптивные - для каждого файла строят таблицу частот символов и с ее помощью сжимают файл. Вместе со сжатым файлом передается таблица символов. Такие алгоритмы достаточно хорошо сжимают большинство файлов, но требуется дополнительная передача таблицы частот символов;
Адаптивные - начинают работать с фиксированной начальной таблицей частот символов (обычно все символы изначально одинаково вероятны) и в процессе работы это таблица изменяется в зависимости от встречаемых символов файла. Преимущества: однопроходность алгоритма; также как и неадаптивные алгоритмы, не требуется передача таблицы частот символов, но достаточно эффективно сжимается широкий класс файлов.

Эвристические алгоритмы сжатия (типа 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      - форматированный текст на русском языке.

Максим Захаров