Метод Хаффмана. Оптимальные префиксные коды

В этом методе при сжатии данных, как уже говорилось выше, каждому символу присваивается оптимальный префиксный код, основанный на вероятности его появления в тексте.

Префиксные коды – это коды, в которых никакое кодовое слово не является префиксом любого другого кодового слова. Эти коды имеют переменную длину.

Префикс, применительно к цепочке a – это какая-либо строка b, где a – конкатенация bc, для некоторой цепочки c.

Оптимальный префиксный код – это префиксный код, имеющий минимальную среднюю длину.

Алгоритм Хаффмана можно разделить на два этапа:

1. определение вероятности появления символов в файле;

2. нахождение оптимального префиксного кода.

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

Далее находятся два символа a и b с наименьшими вероятностями появления и заменяются одним фиктивным символом x, который имеет вероятность появления, равную сумме вероятностей появления символов a и b. Затем, используя эту процедуру рекурсивно, находится оптимальный префиксный код для меньшего множества символов (где символы a и b заменены одним символом x). Код для исходного множества символов получается из кодов замещающих символом путем добавления 0 или 1 перед кодом замещающего символа, и эти два новых кода принимаются как коды заменяемых символов. Например, код символа a будет соответствовать коду x с добавленным нулем перед этим кодом, а для символа b перед кодом символа x будет добавлена единица.

Можно рассматривать префиксные коды как пути в двоичном дереве: прохождение от узла к его левому потомку соответствует 0 в коде, а к правому потомку – 1. Если пометить листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.