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

Алгоритм Хаффмена реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:1. Выписываются в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.2. Последовательно объединяются два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. Затем строится дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.3. Прослеживается путь к каждому листу дерева, с помечанием направления к каждому узлу (например, направо - 1, налево - 0). Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис. 1). Построим, например, кодовое дерево для сообщения со следующим алфавитом: A B C D E 10 5 8 13 10 B C A E D 5 8 10 10 13 A E BC D 10 10 13 13 BC D AE 13 13 20 AE BCD 20 26 AEBCD 46

Рис. 1

Таким образом, получим таблицу для шифрования

A	B	C	D	E

Большим недостатком кода Хаффмена является необходимость иметь таблицы вероятностей для каждого типа сжимаемых данных. Это не представляет проблемы, если известно, что сжимается английский или русский текст; при этом кодеру и декодеру просто предоставляется подходящее для английского или русского текста кодовое дерево. Но в случае, когда вероятность символов для входных данных неизвестна, статистические коды Хаффмена работают неэффективно.

Дата добавления: 2014-01-07