Сайт о сжатии >> Раздел "Cтатьи и исходники"

WIN | KOI | LAT

ИСПОЛЬЗОВАНИЕ МЕТОДОВ СЖАТИЯ ДАННЫХ БЕЗ ПОТЕРЬ ИНФОРМАЦИИ В УСЛОВИЯХ ЖЕСТКИХ ОГРАНИЧЕНИЙ НА РЕСУРСЫ УСТРОЙСТВА-ДЕКОДЕРА

М.А. Смирнов

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Введение *

1. Сравниваемые методы сжатия данных *

2. Известные публикации по теме *

3. Описание программных реализаций сравниваемых методов *

4. Результаты при адаптивном подходе *

5. Результаты при статическом подходе *

Выводы *

Благодарности *

Литература *

В настоящее время большое распространение получили мобильные вычислительные устройства и различная встраиваемая техника. Часто мобильное устройство взаимодействует с некоторым стационарным в рамках модели “клиент-сервер”. Например, так может строиться работа электронных записных книжек, использующихся в качестве терминала для работы с удаленной базой данных. При этом серверу передаются главным образом запросы, а клиенту — требуемые данные, т.е. обмен асимметричен, и основная нагрузка ложится на канал связи от сервера к клиенту. Поэтому при организации информационного взаимодействия между мобильным и стационарным устройством часто возникает проблема эффективного использования канала связи. Экономное кодирование пересылаемых сообщений (сжатие данных) может существенно увеличить реальную пропускную способность канала. Но применение сжатия данных затрудняется тем, что для мобильных или управляемых встраиваемых устройств характерно наличие сравнительно малых вычислительных ресурсов. Декодирование должно требовать небольших затрат оперативной памяти и процессорного времени. При этом требования к алгоритму кодирования (сжатия) значительно менее жесткие.

В настоящей статье приводятся результаты по оценке применимости разных методов сжатия без потерь информации при решении описанной задачи. Сравниваются так называемые “универсальные” методы сжатия данных, т.е. те, которые, как принято считать, не ориентированы на данные специального вида. Более подробно рассматривается вопрос эффективного сжатия текстовых данных, поскольку часто передается и обрабатывается информация именно такого типа. Основное внимание уделяется соотношению между объемом памяти, требуемым для декодирования, и коэффициентом сжатия.

При сравнении были использованы методы сжатия на основе предсказания по частичному совпадению (PPM), на основе преобразования Барроуза-Уилера (BWT), словарные методы семейств LZ77 и LZ78. При этом для статистического кодирования применялось арифметического сжатие. В статье не приводится описания данных методов, интересующийся читатель может обратиться к [1].

Пусть кодируется последовательность длины , составленная из символов конечного алфавита , . Мощность будет обозначаться как , . Конечная последовательность , , называется словом в алфавите .  — длина слова. Процесс кодирования заключается в отображении отдельных слов , составляющих , на множество слов в кодовом алфавите , или кодовых слов. Совокупность всех кодовых слов образует код. Если для всех длина одинакова, то код называется равномерным, а определяет длину кода. Иначе под длиной кода понимается средняя длина кодовых слов на основании вероятности их использования. При посимвольном кодировании все имеют ; соответствующий код часто называют неблочным.

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

Эффективность сжатия как характеристика сокращения размера представления информации относительно исходного будет определяться коэффициентом сжатия . С учетом сложившейся традиции, будет измеряться в “битах на байт” (бит/байт). В этом случае показывается, с помощью какого количества битов в среднем представляется 1 байт исходных (несжатых) данных. Например, бит/байт соответствует сжатию в 2 раза. Чем меньше, тем сжатие сильнее, “лучше”.

Пусть осуществляется посимвольное кодирование , и представляются с помощью равномерного кода. Тогда длина такого кода битов.

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

Таблица 1. Оценки затрат памяти при декодировании для различных методов

Структура данных	, бит	Наиболее вероятное значение , байт
Сжатие при использовании BWT
Блок, полученный при преобразовании
Массив для определения первого столбца отсортированной матрицы
Вектор обратного преобразования
Массив для декодирования “стопки книг”. Структуру можно совместить с (2)		–
Итого
LZ77-код
Собственно декодированный фрагмент
Итого
LZW-код
Словарь. Структура словаря: ссылка на родительскую фразу; последний символ фразы.
Стек для формирования слова (слово формируется справа налево, т.е. последний определяется в первую очередь),  — максимальная длина фразы
Итого
Кодирование по Хаффману (каноническое)
— число нелистовых элементов на уровне , — максимальная длина кодового слова в битах
— алфавит, упорядоченный по длине кодового слова и его числовому значению
— индекс массива такой, что — первый листовой узел (символ) на уровне
Итого
Арифметическое сжатие
Набор счетчиков частот для каждого
Итого

Замечания и пояснения к табл. 1:

1. Оценка не включает расходы по хранению декодированной . При необходимости такого учета следует добавить во всех случаях, исключая LZ77.
2. Для LZW выражение соответствует варианту хранения фраз. Можно дать верхнюю оценку размера словаря как , поскольку в наихудшем случае к имеющимся по определению в словаре фразам при обработке длиной может добавиться фраз.
3. Каноническое кодирование по Хаффману отличается тем, что, во-первых, кодовые слова меньшей длины численно меньше большей длины, и, во-вторых, равной длины численно возрастают в алфавитном порядке соответствующих им символов алфавита [4].
4. Выбор разрядности счетчика частот при арифметическом сжатии зависит от и предполагаемой функции распределения частот

Необходимо признать, что вопрос эффективности алгоритма с точки зрения используемого объема памяти (ОЗУ и/или ПЗУ) и скорости кодирования-декодирования нередко остается за рамками публикаций. Часто сравнение методов и алгоритмов производится только по коэффициенту (степени) сжатия .

Сравнительно пристальное внимание уделяется проблеме экономного декодирования кодов Хаффмана. Среди разработанных алгоритмов наиболее эффективным по критериям размера используемой при декодировании памяти и скорости декодирования является, по-видимому, способ декодирования канонического кода Хаффмана. Различные модификации этого алгоритма рассматриваются, например, в [4, 5].

В [6, 7] описываются варианты алгоритмов с PPM-моделированием низких порядков (порядок ), но не показана зависимость достигаемого от . Также практически опущено сравнение по скорости кодирования/декодирования. Простые экономные схемы контекстного моделирования описываются в [8, 9], но при этом, опять же, не дается развернутого сравнения по скорости, и . В [10] рассматриваются способы ускорения PPM-сжатия за счет увеличения . Предложено кодировать не символ, а его позицию в ранжированном списке символов, встреченных в контексте, а также использовать более быстрые, чем арифметическое сжатие, но менее эффективные по критерию способы кодирования. Вопросу зависимости особого внимания не уделяется.

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

Использовалась авторская реализация PPM. Во всех случаях применялся априорный способ оценки вероятности ухода по методу [1]. Применялись различные PPM-модели. Пусть — это контекстная модель порядка , соответствующая некоторому контексту длины . Параметр — максимальный порядок контекстных моделей, определяющий порядок PPM-модели источника данных. PPM 2-0 обозначена модель, состоящая только из набора и одной . Аналогично, PPM 3-0 включает совокупность и одну . Обозначения PPM 2-1-0 и PPM 3-1-0 расшифровываются сходным образом.

Были рассмотрены два варианта организации структур данных для PPM, именуемые далее как (A), (B). Для обоих вариантов поиск контекстной модели для выполнялся с использованием хеширования. В случае (A) контекстная модель всегда соответствует ровно одному контексту , в случае (B) — набору похожих , где “похожесть” задается хеш-функцией. Для (A) значению хеш-функции может соответствовать хеш-цепочка контекстных моделей , для (B) хеш-цепочка вырождается в одну контекстную модель.

Для варианта (A) использовались структуры:

1. “контекст” (экземпляр создается для встреченного контекста ), имеет поля:

• snum — число различных символов, встреченных в контексте, 1 байт;
• sptr — указатель на массив описаний символов, встреченных в контексте, 2 байт;
• cnext — указатель на следующий “контекст” в хеш-цепочке, 2 байт;
• cnt[] — собственно контекст как массив символов, байт;

2. описание символа (экземпляр создается для символа, встреченного в контексте ):

• sym — собственно символ , 1 байт;
• freq — число появлений в соответствующем контексте , 1 байт.

В целях экономии памяти использовались 8-битовые счетчики. Если содержала 1 символ, то он описывался непосредственно в поле sptr структуры “контекст”.

Для варианта (B) нет необходимости в полях cnext и cnt[] структуры “контекст”. Поэтому количество памяти, доступной для хранения описаний контекстов и описаний символов, больше. Это может компенсировать возможное снижение точности оценки, обусловленное использованием одной для более чем одного контекста.

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

• ptr — ссылка на свободный блок памяти, 2 байт;
• size — размер свободного блока памяти, 2 байт.

Для обеспечения сборки мусора неиспользуемые элементы “контекст” помечались нулевым значением snum и sptr. Неиспользуемые описания символа — нулевым значением freq. При исчерпании памяти устранялись редко используемые и описания символов. При этом в качестве счетчика частоты употребления применялись старшие биты поля cnext.

Для статического режима менеджеры не нужны. Не требуется и поле sptr, поскольку число встреченных в контексте символов известно, и их описание может быть присоединено непосредственно к экземпляру структуры “контекст”.

Собственно кодирование выполнялось с помощью интервального кодера (разновидности арифметического кодера) [1]. Для предотвращения переполнения разрядной сетки все счетчики делились на 2 при достижении максимально допустимой суммы значений всех счетчиков и при достижении счетчика некоторого символа значения .

Использовалась авторская реализация LZW. Фразы кодировались равномерно, длина кода определялась текущим размером словаря. При достижении заданного максимального размера словарь очищался. Для декодирования использовался массив элементов с полями:

• parent — ссылка на родительскую фразу (родительский элемент), 2 байт;
• sym — последний символ фразы, 1 байт.

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

Применялась авторская реализация так называемого метода LZari, при котором кодовые слова LZ экономно представляются с помощью арифметического сжатия. Использовалась типовая схема, при которой длины совпадения и литералы кодировались адаптивно в одном алфавите. Старшие биты кодировались адаптивно, младшие — статически, равномерным кодом. Максимальная .

В статическом режиме использовались заранее построенные таблицы частот для старших битов и для алфавита и .

Применялась авторская модификация программы bzip2, позволившая гибко задавать размер блока для преобразования. В bzip2 для экономного представления результата преобразования используется кодирование “стопка книг” и кодирование по Хаффману. Следует заметить, что реализация кода Хаффмана в bzip2 не рассчитана на блок малой длины, что должно было систематически исказить оценки .

Возможна такая модификация bzip2, что для декодирования будет требоваться примерно байт. Приведенные ниже экспериментальные результаты основываются на этом. Соответствующая программа помечена как bzip2*.

Для статического сжатия текстов был разработан словарный алгоритм, именуемый ниже Dict. Фиксированный словарь Dict состоит из упорядоченных по частоте употребления слов, выделенных из опорного текста. При ограничениях на в словарь вносятся такие слова, использование которых в качестве фраз, как ожидается, даст наименьший . , не найденные в словаре, кодируются посимвольно с помощью арифметического кодера. Найденные арифметически кодируются через номер в словаре, при этом старшие биты номера кодируются исходя из их частоты появления. Младшие биты номера кодируются как равновероятные. Предварительно выполняется обратимое устранение заглавных букв (см. ниже). Самые частые символы-разделители — пробелы — кодируются только при необходимости. По умолчанию считается, что перед словом стоит пробел.

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

1. Замена по фиксированному словарю часто встречающихся последовательностей символов. Если некоторый фрагмент последовательности совпадает с фразой словаря, то он заменяется кодовым словом фразы. Для английского языка использовался словарь, предложенный автором в [1]. Он содержит 45 двухбуквенных фраз, 25 трехбуквенных и 16 двухбуквенных. Для хранения такого словаря и собственно декодирования требуется примерно 300 байт. В качестве кодовых слов применялись незадействованные в ASCII байтовые значения.
2. Устранение заглавных букв. Если слово , рассматриваемое как последовательность , ограниченная некоторыми символами-разделителями (пробел, знаки препинания и т.п.), начинается с заглавной буквы , то:

.

3. Модификация символов-разделителей. Перед символом-разделителем добавляется пробел, что позволяет улучшить сжатие при использовании PPM и, иногда, BWT.

Следует отметить, что, безусловно, все приводимые сравнительные результаты целесообразно рассматривать как довольно грубую оценку. Во-первых, характеристики существенно зависят от типа обрабатываемых данных. Во-вторых, возможна модификация каждого алгоритма и реализации, позволяющая достичь лучших характеристик, и нет оснований считать, что в рамках проведенных экспериментов все методы “были в равных условиях”. В-третьих, равенство по использованию было приблизительным.

Сравнения проводилось на наборе файлов, традиционно используемых для сравнения программ сжатия данных без потерь. Тест был сформирован из файлов классического тестового набора Calgary Compression Corpus и альтернативного набора VYTEST. Описания файлов приведены в табл. 2.

Таблица 2. Описание тестового набора

При проведении экспериментов не учитывались затраты на хранение декодированной . При необходимости этого надо учесть соответствующую поправку для всех реализаций, исключая LZari. Интегральный коэффициент сжатия в зависимости от объема ОЗУ, доступного при декодировании, приведен для всего теста в табл. 3. рассчитывался как обычное среднее коэффициентов для отдельных файлов. не указан для тестов, не проводившихся в силу их очевидной избыточности. Для сравнения даны результаты для архиватора PKZIP версии 2.04g, запускавшегося в режиме максимального сжатия (опция “-ex”). В PKZIP реализован метод LZH с блочной адаптацией кода Хаффмана, что обеспечивает высокую скорость декодирования. Возможна модификация декодера PKZIP, требующая немногим более 32 кбайт ОЗУ.

Таблица 3. Зависимость для тестового набора

Из табл. 3 видно, что при кбайт преимущество по критерию имеют реализации PPM. Максимум достигается для PPM 3-1-0 (A). Следует также отметить, что вариант реализации (A) стабильно обеспечивает лучшее сжатие, чем (B). При порядка 8 кбайт и, очевидно, менее доминирует LZari, что можно было предположить заранее. В табл. 4 приведено сравнительное время декодирования всего набора, при этом время декодирования для PKUNZIP (декодер для PKZIP) принято за 1. Как следовало ожидать, декодирование для PPM в разы медленнее, чем для словарных методов.

Таблица 4. Зависимость для тестового набора

В табл. 5 дана детальная статистика для кбайт. LZari имеет преимущество над PPM только на высоко избыточных файлах. С увеличением отставание может быть устранено за счет использования PPM-модели большего порядка .

Таблица 5. для отдельных файлов при кбайт

Зависимость носит убывающий экспоненциальный характер и может быть хорошо аппроксимирована функцией , где и константы. Например, экспериментальные значения для PPM 3-1-0 (A), приведенные выше в табл. 3, достаточно точно ложатся на график кривой , так что остаются неучтенными всего 4% от вариации . Для рассмотренного тестового набора и диапазона изменения наибольшая скорость убывания — определяется параметром — отмечена у PPM и BWT. (Что согласуется с теоретическими оценками скорости сходимости к энтропии источника информации, известными для рассматриваемых методов.)

На рисунке показана зависимость от объема обработанных данных для book1 при кбайт. При небольшом размере текста разница между для bzip2*, PPM 3-1-0 (A) и PPM 2-1-0 (A) несущественная и составляет менее 10%.

Изменение по мере обработки book1 при кбайт

На примере book1 были рассмотрены варианты схем сжатия с использованием обратимых преобразований текстовых данных. В табл. 6 приведены для вариантов без препроцессинга (далее “БП”). Значения , полученные при устранении заглавных букв и словарной замене (препроцессинг 1, далее “П1”), представлены в табл. 7, полученные при устранении заглавных букв, словарной замене и модификации символов-разделителей (препроцессинг 2, далее “П2”) — в табл. 8.

Таблица 6. для book1 без препроцессинга

Таблица 7. для book1 при препроцессинге 1

Таблица 8. для book1 при препроцессинге 2

В табл. 9 показана зависимость для book1 без препроцессинга. Табл. 10 иллюстрирует изменение при использовании препроцессинга.

Таблица 9. для book1 без препроцессинга

Таблица 10. для book1 при препроцессинге

Использование препроцессинга в среднем существенно улучшает сжатие для всех алгоритмов. Наибольший эффект достигается для PPM 2-1-0 — в ряде случаев отмечено уменьшение на 25%. Но в рамках рассмотренных алгоритмов PPM и диапазона изменения применение препроцессинга, как правило, замедляет декодирование в 1.1-1.9 раза.

Статический режим предполагает хранение и использование фиксированной модели (словаря). Это специфическая задача, которая, по-видимому, должна решаться с максимальным учетом специфики данных, имеющихся ресурсов, особенностей аппаратного и, возможно, программного обеспечения. Поэтому даются результаты, полученные на примере сжатия только текстового файла book1. Сжатие на основе обычного BWT в статическом режиме невозможно, метод LZW не рассматривался в силу сравнительно плохих характеристик. Во всех случаях первые 512 кбайт исходного файла использовались для создания и настройки модели (словаря), которая затем применялась без адаптации при сжатии оставшейся части файла размером кбайт. Результаты для вариантов без препроцессинга сведены в табл. 11, результаты для сжатия с препроцессингом — в табл. 12 (для Dict препроцессинг не имеет смысла, поэтому вариант не рассматривался).

Таблица 11. в статическом режиме без препроцессинга

Таблица 12. в статическом режиме с препроцессингом

Алгоритмы PPM 2-1-0 и PPM 3-1-0 обеспечивают лучшее сжатие. При использовании препроцессинга любого типа сжатие, как правило, улучшается (соответствует уменьшению ). Зависимость имеет убывающий экспоненциальный характер.

В табл. 13 показано, как изменяется . За 1 принято при использовании PKUNZIP. Видно, что, как и при адаптивном подходе, при использовании препроцессинга может увеличиваться на десятки процентов.

Таблица 13. в статическом режиме

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

При адаптивном сжатии в случае наличия до 16 кбайт ОЗУ в общем случае целесообразно применение алгоритма типа LZ77. При большем возможны варианты, и выбор зависит от типа данных и требований к . Если нет очень жестких ограничений по , и обрабатываются текстовые данные, целесообразно использовать алгоритм сжатия на основе контекстного моделирования типа PPM. При объеме  кбайт разумно применять модель с длинами контекстов 2, 1, 0 (PPM 2-1-0), при имеет смысл рассмотреть PPM 3-1-0 или даже более сложные схемы. Разница в коэффициенте сжатия для алгоритмов типа LZ77 и PPM может составлять при этом 25% и более.

При статическом подходе, предполагающем хранение модели источника данных (словаря) в ПЗУ и минимальное использование ОЗУ, наблюдается в целом сходная картина в случае сжатия текстовых данных. В случае жестких ограничений на и доступный объем ПЗУ следует применять словарные алгоритмы. Иначе целесообразно проанализировать оправданность использования алгоритма на основе PPM. Но, скорее всего, даже при тщательном построении алгоритма и эффективной реализации скорость декодирования для PPM будет в разы меньше, чем для словарных схем. Перспективным является словарный алгоритм, при котором фразами являются естественные слова языка.

Как при адаптивном, так и при статическом подходе использование специальных обратимых преобразований совместно с основным алгоритмом сжатия может существенно улучшить сжатие текстовых данных — отмечается уменьшение на 5-25%. Но, как правило, это замедляет декодирование в 1.1-1.9 раза.

Спасибо Вадиму Юкину за ряд полезных замечаний и советов.

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2002. – 384 с.
2. Gallager R.G. Variations on a theme by Huffman. IEEE Transactions on Information Theory, 24(6):668-674, Nov. 1978.
3. Burrows M., Wheeler D.J. A Block-sorting Lossless Data Compression Algorithm. SRC Research Report 124, Digital Systems Research Center, Palo Alto, May 1994.
4. Moffat A., Turpin A. On the Implementation of Minimum Redundancy Prefix Codes. IEEE Transactions on Communications, 45(10):1200-1207, Oct. 1997.
5. Hirschberg D., Lelewer D. Efficient decoding of prefix codes. Communications of the ACM, 33(4):449-459, 1990.
6. Lelewer D.A., Hirschberg D.S. Streamlining Context Models for Data Compression. Proceedings of IEEE Data Compression Conference, Snowbird, Utah, Apr. 1991, pp. 313-322.
7. Lelewer D.A., Hirschberg D.S. An Order-2 Context Model for Data Compression With Reduced Time and Space Requirements. Technical Report N90-33, Department of Information and Computer Science, University of California, Irvine, 1990.
8. Langdon G., Rissanen J. A Double-Adaptive File Compression Algorithm. IEEE Transactions on Communications, 31(11):1253-1255, Nov. 1983.
9. Bell T., Witten I., Cleary J. Modeling for Text Compression. ACM Computing Surveys, 21(4):557-591, Dec. 1989.
10. Howard P.G. The design and analysis of efficient lossless data compression systems. PhD thesis, Brown University, Providence, Rhode Island, 1993.