В.Д. Валединский - Избранные главы лекций по программированию (1114957), страница 8
Текст из файла (страница 8)
Действительно, если бы для текущего набора символовсуществовало другое кодирующее дерево, дающее меньшую длину, то «разделив» обратно объединенный символ и добавив в это дерево вершины a и b, мы получили бы меньшую длину кодовой последовательности идля исходного входного потока, что невозможно в силу предположения об оптимальности начального состояниядерева To .Повторяя эти рассуждения и отождествляя следующие две вершины с минимальными весами, мы и далеебудем одинаково уменьшать длины выходных кодирующих последовательностей, пока в кодирующих деревьяхне останется по две концевых вершины (отождествляющих в себе в сумме все исходные символы). При этомдерево Хаффмана будет давать кодирующую последовательность в n бит, так как два оставшихся кода есть 0 и1.
Оставшееся дерево To является оптимальным и также дает кодовую последовательность длины n, посколькуменьше просто быть не может (единственный выбор для оставшихся двух символов есть также коды 0 и 1). Таккак каждый раз кодовые последовательности уменьшались на одинаковую величину, их исходные длины такжебыли одинаковы. Следовательно, дерево Хаффмана также давало кодирующую последовательность наименьшейдлины. Очевидным недостатком метода Хаффмана является необходимость передавать декодировщику таблицу частот символов вместе с кодирующей последовательностью, что уменьшает суммарный коэффициент сжатия.Существует адаптивный вариант алгоритма Хаффмана, который не требует передачи дерева (или частотнойтаблицы) вместе с закодированными данными.
Идея этого алгоритма заключается в адаптивном перестроении дерева с учетом поступивших символов при кодировании и соответствующем преобразовании дерева придекодировании.4.3. Адаптивный вариант алгоритма ХаффманаПусть мы имеем некоторое дерево Хаффмана. Пронумеруем вершины этого дерева «слева-направо, снизувверх», т. е. нумерация начинается с элементов самого нижнего уровня дерева, потом переходит на предыдущийуровень, и т. д. Корень дерева получает максимальный номер.Будем называть дерево упорядоченным, если веса вершин не убывают в порядке построенной нумерации.Построим начальное дерево Хаффмана, считая, что все символы имеют вес 1. Теперь при появлении новогосимвола мы должны перестроить дерево так, чтобы сохранить свойство упорядоченности.
Во-первых, надо увеличить вес соответствующей концевой вершины и всех родителей по ветви, ведущей к корню. Если после этогодерево останется упорядоченным, то ничего больше делать не надо. Если же вес какой-либо вершины A становится больше веса правого соседа (по нумерации), то среди правых соседей (по нумерации) ищется последний,вес которого меньше веса A, и эта вершина (вместе со своими потомками) обменивается с A.
Затем корректируются веса по ветвям, ведущим к корню от переставленных вершин. Указанный процесс продолжается, покадерево не станет упорядоченным.Кодирование и декодирование по адаптивному варианту алгоритма происходит единообразно:1. Инициализируем дерево равномерным распределением символов (все символы имеют количество повторений 1).2. Получаем очередной символ (или код) и кодируем (раскодируем) его в соответствии с текущим состояниемдерева.3.
Добавляем единицу к весу вершины, соответствующей только что полученному символу, и перестраиваемдерево на основе для сохранения свойства упорядоченности.4. Если есть еще символы (коды) во входном потоке, то перейти к пункту 2, иначе закончить работу.20Естественно, адаптивный алгоритм не дает оптимальной кодовой последовательности.
Однако он обладаетрядом преимуществ. Во-первых, не требуется передавать таблицу частот. Во-вторых, он обладает свойствомнастройки на текущее распределение частот. Рассмотрим следующий искусственный, но показательный пример.Пусть входная последовательность содержит достаточно длинные цепочки одинаковых байт, при этом в целомраспределение частот является равномерным. Для такой последовательности обычный алгоритм Хаффманане предложит ничего лучшего, чем обычные восьмибитные коды байтов.
Однако в адаптивном варианте оннастроится на локальные частотные характеристики и назначит повторяющимся символам более короткие коды,что может дать выигрыш для файла в целом.4.4. Арифметическое кодированиеВ основе алгоритма арифметического кодирования лежит очень простая и красивая идея. Входной потокбайтов рассматривается как запись некоторого числа, в которой входные символы играют роль «цифр». Алгоритм переводит эту запись в двоичное представление следующим образом.Пусть мы имеем входную последовательность длиной n байт.
Обозначим частоту появления байта со значением k в этой входной последовательности через αk . Здесь под частотой мы понимаем отношение количества255Pпоявлений данного фиксированного байта к количеству всех байт. Таким образом, αk ∈ [0, 1],αk = 1, иk=0количество появлений данного байта есть pk = nαk .Разобьём отрезок s0 = [0, 1] на подотрезки, равные по длине αk , и сопоставим эти отрезки соответствующимзначениям байтов входной последовательности.Возьмём первый байт входного потока и рассмотрим соответствующий ему отрезок (обозначим его s1 ).
Разобьём отрезок s1 пропорционально частотам αk (аналогично тому, как был разбит отрезок s0 ). Теперь возьмемследующий входной байт и рассмотрим соответствующий ему отрезок s2 ⊂ s1 . Далее процесс продолжается аналогично (т. е. разбиваем текущий выбранный отрезок пропорционально частотам и выбираем в нём следующийотрезок по новому поступившему байту входной последовательности). В результате мы получим последовательность вложенных друг в друга отрезков s0 ⊃ s1 ⊃ s2 ⊃ · · · ⊃ sn .
Результатом кодирования является любоечисло, принадлежащее последнему выбранному отрезку sn .Декодирование производится достаточно просто. Для этого надо взять кодирующее число и найти тот отрезок разбиения первого уровня, которому оно принадлежит. Номер этого отрезка есть первый байт исходногонабора данных. Затем, разбив найденный отрезок, исходя из частот, можно определить номер того отрезка разбиения второго уровня, которому принадлежит число и т. д. Для устранения неоднозначности кодирования идекодирования следует исключить из проверки одну из границ отрезков (например, правую).Для возможности декодирования следует знать таблицу частот и общее количество байтов исходной последовательности.
В противном случае неясно, в какой момент прекращать процесс декодирования.Опишем алгоритм построения кодирующей дроби в виде псевдокода. Пусть элементы массива a[i] задаютточки границ отрезков частотного разбиения для байта, т. е. αi = a[i+1]-a[i], а функция NextByte() читает ивозвращает очередной байт входной последовательности, либо значение EOI (End Of Information) при окончаниинабора данных. Описанный выше алгоритм выглядит так:Left = 0;Right = 1;while ((K = NextByte()) != EOI){D = Right - Left;Right = Left + D * a[K+1];Left = Left + D * a[K];}По окончании этого цикла в качестве кодирующей дроби можно взять любое число x, удовлетворяющееусловию Left 6 x < Right.Декодирование производится обращением описанного выше процесса.X = <кодирующая дробь>N = <общее число символов в исходном файле>while (N--){K = Interval(X);// найти номер интервала, содержащего XOutput(Symbol(K)); // вывести K-й символD = a[K+1] - a[K];// длина интервала для K-го символаX = (X - a[K]) / D; // преобразуем дробь для следующего символа}21Алгоритм арифметического кодирования может привести к поразительным результатам.
Например, еслипри кодировании окажется, что окончательный отрезок содержит точку 0.510 = 0.12 , то мы получим выходнойкод длиной всего в 1 бит, не считая накладных расходов в виде таблицы частот и количества входных байтов.Однако в общем случае на это нельзя полагаться, и возникает резонный вопрос: а почему этот алгоритм в общемслучае способен сжимать информационно избыточные наборы данных?Мы ограничимся здесь только доказательством факта наличия сжатия.
Вопрос о величине сжатия зависит отстепени неравномерности распределения значений байтов во входной последовательности и требует привлечениядополнительных понятий, выходящих за рамки нашего изложения. Для доказательства нам потребуется однопростое свойство выпуклых функций.Лемма 4.3. Пусть функция f (x) является выпуклой вниз на некотором интервале (a, b). Тогда для любогонабора x1 , . . . , xm ∈ (a, b) выполнено соотношение!mm1 X1 Xf (xk ) > fxk ,mmk=1k=1причём равенство достигается только при x1 = x2 = · · · = xm .
Доказательство легко проводится индукцией по m с учётом хорошо известного неравенства для выпуклых вниз функций: αf (x1 ) + (1 − α)f (x2 ) > f (αx1 + (1 − α)x2 ), где α ∈ (0, 1). Теорема 4.4. Пусть входная последовательность, состоящая из n байт (или 8n бит), имеет неравномерное распределение частот значений отдельных байтов. Тогда кодирующая дробь метода арифметическогокодирования может быть представлена менее чем 8n битами.
Пусть αk — длины отрезков исходного разбиения и pk = αk n — количество появлений байта со значениемk. Легко видеть, что длина последнего кодирующего отрезка равнаl=Yαpkk .αk 6=0Для построения кода нам нужно найти число, принадлежащее такому отрезку и имеющее по возможностинаименьшее количество бит в своем двоичном представлении. Для того, чтобы в произвольном отрезке длиныl нашлась двоичная дробь, содержащая d значащих разрядов, достаточно выполнения неравенства 2−d 6 l.Отсюда получаем d > − log2 l. Так как нас интересует дробь с наименьшим количеством значащих разрядов, топринимаем d ≈ − log2 l за длину выходного кода алгоритма.
Имеемd ≈ − log2 l = −Xαk 6=0log2 αpkk = −Xαk 6=0nαk log2 αk 6 −256n1 Xαk log2 αk .256αk 6=0Функция f (x) = x log2 x является выпуклой вниз при x > 0, поскольку ее вторая производная положительна:f ′′ (x) = 1/x. Воспользовавшись леммой для оценки последней суммы, имеемα0 + . . . + α255α0 + . . . + α2551d < −n · 256log2= −n log2= 8n.256256256Здесь поставлено строгое неравенство, так как по условию теоремы αk не все одинаковы в силу неравномерности распределения частот.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
