5. Оптимальное кодирование, код Хаффмена.

Код С₀ называется оптимальным, если R(S, C₀)<=R(S,C), где С – код, S - источник, R – избыточность кодирования. Простейшие алгоритмы сжатия, называемые также алгоритмами оптимального кодирования, основаны на учете распределения вероятностей элементов (слов) исходного сообщения (текста, изображения, файла). На практике обычно в качестве приближения к вероятностям используют частоты встречаемости элементов в исходном сообщении.

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

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

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

6. Построение префиксных кодов, код Фано.

Префиксные коды - это такие коды, в которых ни одна более короткая комбинация не является началом более длинной комбинации, что позволяет производить однозначное декодирование, даже если последовательность кодов не содержит разделителей между кодами. Например, код, состоящий из слов: 00, 01, 110, 111 – префиксный. А код из слов 0, 10, 11, 110 – не является префиксным (слово 11 является началом для слова 110).

Код называется префиксным полным, если к нему нельзя добавить слово без нарушения префиксности. Говоря о префиксности нельзя не упомянуть и неравенство Крафта, которое задаёт такие ограничения, чтобы код был префиксным. Итак, необходимым и достаточным условием существования префиксного кода объема M с длинами кодовых слов l,...,lM является выполнение неравенства . Отметим, что данная теорема говорит нам лишь о существовании кода, но не указывает на его конкретный вид.

Докажем необходимость: Докажем, что неравенство верно для любого префиксного кода. Рассмотрим двоичное кодовое дерево произвольного префиксного кода объема M с длинами кодовых слов l₁ ,...,l_М . Выберем целое число L , такое, что L ≥ max l . На этом ярусе мы имеем 2^L вершин. Заметим, что вершина дерева, расположенная на ярусе l_i ,имеет 2 потомка на ярусе l_i+1 , 4 потомка на ярусе l_i+2 , и т.д. Т.е. на ярусе L будет 2^L-l потомков этой вершины l_i, а т.к. код префиксный, то множества потомков используемых в коде вершин не пересекаются, поэтому суммарное число потомков на ярусе L используемых в коде вершин не превышает общего числа вершин яруса L . Иными словами, . Разделив это неравенство на 2^L получим неравенство Крафта, т.е. оно верно для любого префиксного кода.

Докажем достаточность: Нам надо показать, что мы всегда сможем построить префиксный код, соответствующий неравенству Крафта. Первое кодовое слово выберем из узлов яруса l₁. Выбранная вершина породит потомков яруса, которых мы не сможем в дальнейшем использовать для не нарушения префиксности при выборе узла на ярусе l_2. Т.е. на ярусе l₂ останется доступных для выбора узлов. Из неравенства Крафта для М=2 нетрудно получить(умножив его на ), что >=1, т.е. доступные узлы есть. Действуя аналогично дальше, покажем что есть узел и для яруса l_M. На этом ярусе для не нарушения префиксности нам можно использовать узлов. Если мы умножим левую и правую часть неравенства Крафта на , то, после несложных преобразований, получим, что наше число >=1, т.е. хотя бы один узел на последнем нужном ярусе найдется. Т.е. мы можем построить префиксный код, удовлетворяющий неравенству Крафта.

Одним из конкретных применяемых методов построения префиксных кодов является метод кодирования по Фано. Алгоритм следующий: исходное множество символов упорядочивается по невозрастанию частот. Затем, список символов делится на две части так, чтобы суммы частот обеих частей были равны, либо разница между суммами минимальна из всех возможных вариантов, при этом кодовым комбинациям одной части дописывается 1, другой-0. Далее, в каждой части смотрится, сколько символов в неё попало. Если 1, то кодирование для этого символа считается завершённым. Если несколько, то с ними повторяется абсолютно такая же процедура. Кодирование заканчивается, когда все символы будут закодированы. Смысл в том, что словам с большей вероятностью появления соответствуют более короткие комбинации символов.