Алгоритм Хаффмана: построение дерева для заданной фразы
Что такое алгоритм Хаффмана?
Алгоритм Хаффмана — это метод сжатия данных, который использует дерево Хаффмана для оптимального кодирования символов в заданной последовательности.
Постановка задачи
Для фразы «королева кавалеру подарила каравеллу» необходимо построить дерево Хаффмана и определить коды для каждого символа.
Подготовка к построению дерева
Сначала необходимо подсчитать частоту встречаемости каждого символа в заданной фразе:
- к — 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
Заключение
Алгоритм Хаффмана позволяет эффективно сжимать данные, используя оптимальное кодирование символов. Построение дерева Хаффмана и кодирование символов требует определенных шагов, но в итоге позволяет сократить объем информации и повысить скорость передачи данных.
