Алгоритм Хаффмана: построение дерева для заданной фразы

Что такое алгоритм Хаффмана?

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

Постановка задачи

Для фразы «королева кавалеру подарила каравеллу» необходимо построить дерево Хаффмана и определить коды для каждого символа.

Подготовка к построению дерева

Сначала необходимо подсчитать частоту встречаемости каждого символа в заданной фразе:

• к — 5 раз
• о — 4 раза
• р — 3 раза
• л — 3 раза
• е — 2 раза
• а — 4 раза
• в — 2 раза
• у — 2 раза
• п — 1 раз
• д — 1 раз
• и — 1 раз
• а — 1 раз

Построение дерева Хаффмана

Для построения дерева Хаффмана необходимо объединять символы с наименьшей частотой встречаемости и строить новые вершины дерева, пока все символы не будут объединены в одной вершине.

Шаг 1

Символы с наименьшей частотой встречаемости: п, д, и

Объединяем их в вершину с суммарной частотой 3:

(п, д, и)
/
п (д, и)
/
д, и

Шаг 2

Символы с наименьшей частотой встречаемости: в, у

Объединяем их в вершину с суммарной частотой 4:

(в, у)
/
в у

Шаг 3

Символы с наименьшей частотой встречаемости: е, а

Объединяем их в вершину с суммарной частотой 6:

(е, а)
/
е а

Шаг 4

Символы с наименьшей частотой встречаемости: п, д, и | в, у

Объединяем их в вершину с суммарной частотой 7:

(п, д, и)
/
(в, у) (е, а)
/ /
в у е а

Шаг 5

Символы с наименьшей частотой встречаемости: р, л, а | в, у

Объединяем их в вершину с суммарной частотой 9:

(р, л, а)
/
(в, у) (п, д, и | е, а)
/ /
в у (п, д, и) (е, а)
/ /
п (д, и) а
/
д, и

Шаг 6

Осталось объединить остальные символы:

(к, о, р, л, а)
/
(в, у) (п, д, и | е, а)
/ /
в у (п, д, и) (е, а)
/ /
п (д, и) е а
/
д, и

Кодирование символов

Кодирование символов происходит следующим образом:

• к — 00
• о — 01
• р — 100
• л — 101
• е — 1100
• а — 1101
• в — 1110
• у — 1111
• п — 10000
• д — 10001
• и — 10010
• к — 10011

Таким образом, для заданной фразы «королева кавалеру подарила каравеллу» получаем следующие коды символов:

к — 00, о — 01, р — 100, л — 101, е — 1100, а — 1101, в — 1110, у — 1111, п — 10000, д — 10001, и — 10010

Заключение

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