Способ кодирования носит название кода Шеннона-Фано

Рассмотрим очень упрощенную ситуацию, в которой справедливо утверждение «символ несет в себе тем больше информации, чем меньше вероятность его появления».

Представим текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Представим вероятности появления этих символов следующим образом:

А Б В Г Д Е Ж З И К Л М Н О П Р

0,2 0,150,150,10,080,08 0,060,040,030,022 0,018 0,016 0,014 0,014 0,013 0,013

Сумма этих вероятностей составляет, естественно, единицу. Разбиваем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис.1). В данном примере это будут группы символов А–В и Г–Р. Группы символов называются вершинами или узлами (nodes), а сама конструкция из этих узлов – двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой – цифрой 1.

Снова разобьем первую группу (А–В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй – цифру 1. Будем повторять эту операцию до тех пор, пока на каждой вершине нашего «дерева» не останется по одному символу. Полное дерево для нашего алфавита будет иметь 31 узел.

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность р=0.2,.. кодируется всего двумя битами, а буква Р, имеющая вероятность р=0,013, кодируется шестибитовой комбинацией.

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

Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах Хаффмана. В коде Хаффмана каждая буква исходного текста представляется в архиве кодом переменной длины. Более частые буквы представляются короткими кодами, менее частые – длинными. Коды, используемые в сжатом тексте должны подчиняться свойствам префикса, а именно: код, использованный в сжатом тексте, не может быть префиксом любого другого кода.

Коды префикса могут быть найдены посредством дерева, в котором каждый лист соответствует одной букве алфавита источника. Код префикса для буквы может быть прочитан при обходе дерева от корня к этой букве, где 0 соответствует выбору левой его ветви, а 1 – правой. Дерево кода Хаффмана есть дерево с выровненным весом, где каждый лист имеет вес, равный частоте встречаемости буквы в исходном тексте, а внутренние узлы своего веса не имеют. Дерево в примере будет оптимальным, если частоты букв А, В, С и D будут 0,125, 0,125, 0,25 и 0,5 соответственно.

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

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

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