Сайт о сжатии  >>  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. Авторский проект.
---------------------------------------------------------

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

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

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

Эвристические алгоритмы сжатия (типа LZ77, LZ78), как правило, ищут повторяющиеся строки в файле, либо строят словарь как уже встречавшихся фраз, так и фраз, которые наиболее вероятно могут появится в тексте.

Обычно такие алгоритмы обладают целым рядом специфических параметров (размер буфера, максимальная длина фразы, размер рассматриваемого контекста и т.п.), подбор которых зависит от опыта автора алгоритма, и эти параметры подбираются так, чтобы добиться оптимального сочетания времени работы, коэффициента сжатия и широты класса хорошо сжимаемых файлов.

При подборе этих параметров можно заметить, что для различных файлов (текстовые, двоичные, базы данных) оптимальны различные сочетания параметров, не говоря уже о том, что разные алгоритмы оптимальны для разных классов исходных файлов. 

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

Вся тонкость заключается в решении о принадлежности данного файла к тому или иному классу. Можно заметить, что для файлов того или иного класса свойственно определенное распределение частот символов. Конечно, для каждого файла распределение частот уникально, но у файлов одного класса эти распределения не сильно различаются. Таким образом проблема сводится к определению вида распределения символов к которому ближе всего в данный момент распределение символов обрабатываемого файла. 

Мерой близости одного распределения частот символов к другому может служить количество информации. В отличие от Шенноновской энтропии, существует несколько различных определений количества информации. Это связано с условиями, которые накладываются на нее. Этим условиям удовлетворяет несколько различных функций. Не вдаваясь в математические подробности, скажем самое главное: эта функция должна обращаться в ноль при равенстве распределений и положительной в других случаях. 

Примерная схема суперадаптивного сжатия:

  1. Нам известны несколько различных алгоритмов сжатия и распределения частот для которых они оптимальны. Стартуем с фиксированного распределения частот и соответствующего ему алгоритма.
  2. Используя текущий алгоритм кодируем 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      - форматированный текст на русском языке.
Максим Захаров
Последнее обновление: 30-April-2020

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

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

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

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

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

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

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

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