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

Maxime, 19.4.98, 24.04.93

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


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



12.03.2002
Для автоматического определения кодировки и языка документов в поисковой машине MnogoSearch наиболее подходящим оказалось следующее определение количества информации:
            M       2
         SUM     log  ( Pi/Qi )
            i=1

При выборе языка и кодировки, имеющих наименьшее значение количества информации, вычисленного по этой формуле, достигалась наименьшая ошибка в определении языка и кодировки по частоте наиболее часто встречающихся N-грамм (N <= 5).
Изменена 19.03.2011 06:45 MSK Яндекс цитирования Рейтинг@Mail.ru  Юридическая помощь