Алгоритмы сжатия данных при передаче через интернет

Адаптированные и неадаптированные модели

В порядке функционального соответствия декодер должен иметь доступ к той же модели, что и кодировщик. Для достижения этого есть три способа моделирования: статичное, полуадаптированное и адаптированное.

Статичное моделирование использует для всех текстов одну и ту же модель. Она задается при запуске кодировщика, возможно, на основании образцов типа ожидаемого текста. Такая же копия модели хранится вместе с декодером. Недостаток состоит в том, что схема будет давать неограниченно плохое сжатие всякий раз, когда кодируемый текст не вписывается в выбранную модель, поэтому статичное моделирование используют только тогда, когда важны в первую очередь скорость и простота реализации.

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

Адаптированное (динамическое) моделирование уходит от связанных с этой передачей расходов. Первоначально и кодировщик, и декодер присваивают себе некоторую пустую модель, как если бы все символы были равновероятными. Кодировщик использует эту модель для сжатия очередного символа, а декодер – для его «разворачивания». Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется уже на основании измененной модели, а затем сам вновь изменяет модель. Кодирование происходит аналогичным раскодированию образом, при этом поддерживает идентичную модель за счет применения такого же алгоритма ее изменения, обеспеченного отсутствием ошибок. Используемая модель, которую к тому же не нужно передавать явно, будет хорошо соответствовать сжатому тексту. Адаптированные модели представляют собой элегантную и эффективный метод, и обеспечивают компрессию, которая, по крайней мере, не уступает сжатию, производимому неадаптированными схемами. Оно может быть даже значительно лучше, чем у плохо соответствующих текстам статичных моделей. Адаптированные модели, в отличии от полуадаптиpованных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучше сжимающими. Однако описанная схема компрессии имеет связанное с ее спецификой уязвимое место: модель никогда не передается явно, поэтому сбой происходит только в случае нехватки под нее памяти при динамическом проектировании модели.

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

Кодирование

Задача замещения символа с вероятностью p приблизительно –log2p битами называется кодированием.

Это узкий смысл понятия, а для обозначения более широкого будем использовать термин «сжатие». Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток битов, на основе которого этот символ может быть затем декодирован, если используется тот же набор вероятностей, что и при кодировании. Вероятность появления любого конкретного символа в разных частях текста может быть разной.

Алгоритм Хаффмана

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

На следующем шаге то же происходит с узлами Б и В, так как теперь эта пара имеет самый меньший вес в дереве. Создается новый узел с весом 13, а узлы Б и В удаляются из списка свободных. После всего этого дерево кодирования выглядит так, как показано на рис. 1.

Рис. 1. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.

Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 2.

Рис. 2. Окончательное дерево кодирования Хаффмана

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

Дня данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А              0

Б              100

В              101

Г              110

Д              111

Поскольку ни один из полученных кодов не является префиксом другого, они могут быть однозначно декодированы при чтений их из потока. Кроме того, наиболее частый символ сообщения А закодирован наименьшим количеством битов, а наиболее редкий символ Д - наибольшим.

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

Арифметическое кодирование

Арифметическое сжатие - достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 - включается, 1 - нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст "КОВ.КОРОВА" (что, очевидно, означает "коварная корова"). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны: