Главная » Java, Структуры данных и алгоритмы » Алгоритм кодирования Хаффмана

0

начинает работу с выбора в исходной строке ^символа d, который станет корнем одноузлового бинарного дерева. Алгоритм выполняет серию проходов. При каждом проходе выбираются два бинарных дерева с наименьшими частотами и соединяются в одно бинарное дерево. Этот процесс продолжается до тех пор, пока не получим одно бинарное дерево (см. фрагмент кода 11.8).

Каждая итерация рабочего цикла алгоритма Хаффмана может быть реализована за 0(\ogd) времени с помощью приоритетной очереди, представленной пирамидой. Кроме того, эта итерация извлекает из Q два узла, а добавляет один. Этот процесс повторяется d – 1 раз до тех пор, пока в Q не останется только один узел. Таким образом, алгоритм выполняется за 0(п + dlog d) времени. Хотя полное доказательство верности этого алгоритма выходит за рамки книги, заметим, что идея заключается в возможности конвертации любого оптимального кода в другой оптимальный код, в котором кодовые слова, используемые для символов а и Ъ с невысокой частотой употреблений, отличаются друг от друга только последним битом. Заменяя а и b на с, можно вывести следующее.

Утверждение 11.6. Алгоритм Хаффмана создает оптимальный префиксный код для строки длиной п, содержащей d различных символов, за 0(п + dlogd) времени.

Алгоритм Huffman^):

Input: строка А" длиной и, имеющая d отличных (друг от друга) символов.

Output: кодовое дерево для X.

Вычислить частоту f(c) для каждого символа с в X

Инициировать приоритетную очередь Q for each символа с в X do

Создать состоящее из одного узла бинарное дерево Т, хранящее с. Ввести в Q дерево Т с ключом f(c).

while Q.size() > 1 do fi <- Q.minKey()

<- Q.removeMin() f2 <- O.minKeyO T2 <- Q.removeMin()

Создать новое бинарное дерево Т с левой ветвью и правой Г2. Ввести в О дерево Т с ключом f, + fe. return tree Q.removeMin()

Фрагмент кода 11.8.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии