Дерево Хаффмана – это очень полезная структура данных, которая применяется в сжатии данных и кодировании информации. Она была разработана Дэвидом Хаффманом в 1952 году и до сих пор остается актуальной и эффективной.
Построение дерева Хаффмана – это процесс создания бинарного дерева, в котором каждая внутренняя вершина имеет двух детей, а каждый лист представляет собой символ (или более сложную иерархию, в случае кодирования более чем одного символа).
Практическое применение этой структуры данных включает сжатие файлов, кодирование сообщений или создание алгоритмов сжатия. Построение дерева Хаффмана может быть достаточно сложным процессом, но с нашей пошаговой инструкцией и примерами все станет намного понятнее.
Построение дерева Хаффмана
Построение дерева Хаффмана включает несколько шагов:
- Определение частоты встречаемости каждого символа во входных данных.
- Создание списка, в котором каждый символ представлен в виде листа дерева. Частота символа становится его весом.
- Построение дерева Хаффмана путем объединения двух вершин с наименьшими весами и создания новой вершины с весом, равным сумме весов объединенных вершин. Повторное выполнение этого шага до тех пор, пока не будет построено итоговое дерево.
- Присвоение кода каждому листу дерева: левому потомку соответствует 0, а правому – 1.
Пример построения дерева Хаффмана:
Допустим, у нас есть следующая последовательность символов и их частот:
А – 5 раз
Б – 3 раза
В – 1 раз
Г – 2 раза
Сначала создадим список с листьями дерева:
A:5
Б:3
В:1
Г:2
Затем объединяем две вершины с наименьшими весами (В и Г) и создаем новую вершину:
А:5
Б:3
ВГ:3
Повторяем этот шаг:
А:5
АБГ:8
И окончательно получаем дерево Хаффмана:
АБГ:8 / \ А:5 БГ:3 / \ Б:3 В:1
Каждому листу соответствует префиксный код:
А: 0
Б: 10
В: 110
Г: 111
Таким образом, мы создали оптимальный код для каждого символа и можем использовать его для сжатия данных.
Инструкция с примерами и пошаговым объяснением
Шаг 1: Подсчет частоты встречаемости символов в исходном наборе данных. Например, для строки «aabbc» мы подсчитываем, что символ «a» встречается 2 раза, символ «b» — 2 раза и символ «c» — 1 раз.
Шаг 2: Создание листов дерева для каждого символа с их частотой встречаемости. Присваиваем каждому листу символ и его частоту. В нашем примере создаем листы для символов «a» (2), «b» (2) и «c» (1).
Шаг 3: Создание вспомогательного узла суммой частоты листьев. Узел считается вспомогательным, потому что он не содержит символа. Суммируем частоты соседних листьев и создаем вспомогательный узел с этой суммой. Получаем вспомогательный узел с частотой 3.
Шаг 4: Присоединение вспомогательного узла к двум наименьшим узлам. Выбираем два узла с наименьшей суммой частоты и создаем новый узел с их суммой. При этом, узел с наименьшей суммой оказывается левым потомком, а узел с большей суммой — правым потомком. В нашем примере присоединяем вспомогательный узел (3) к листам «b» (2) и «c» (1), получая новый узел с суммой 3.
Шаг 5: Повторяем шаги 3 и 4, пока все узлы не объединятся в одно дерево. Каждая итерация создает новый узел объединения суммы двух наименьших узлов и становится новым наименьшим узлом для следующей итерации. В нашем примере следующим узлом будет новый узел с суммой 5, объединяющий узел с символом «a» (2) и созданный в предыдущей итерации (3).
Шаг 6: Создание префиксного кода для каждого символа в дереве. Префиксный код — это бинарное представление каждого символа, где левая ветвь помечена как «0», а правая — как «1». Каждому символу присваиваем его префиксный код, следуя пути от корня до соответствующего листа. В нашем примере символу «a» присваиваем код «0», символу «b» — «10» и символу «c» — «11».
Шаг 7: Сжатие данных с использованием созданного префиксного кода. Заменяем каждый символ в исходном наборе данных его префиксным кодом. Например, строка «aabbc» будет сжата в «0010110».
Теперь вы знаете, как построить дерево Хаффмана для сжатия данных и использовать его для раскодирования. Попробуйте использовать этот метод на различных наборах данных и экспериментируйте с разными символами и их частотами.
Примеры и шаг за шагом
В этом разделе мы рассмотрим построение дерева Хаффмана на примере набора символов и их весов. Шаг за шагом пройдем по всем этапам алгоритма и построим дерево Хаффмана.
Для начала, рассмотрим следующий набор символов и их весов:
| Символ | Вес |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
Шаг 1: Сортировка символов по возрастанию их весов:
| Символ | Вес |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
Шаг 2: Объединение двух символов с минимальными весами в один узел. Пересчитываем вес нового узла:
| Символ/Узел | Вес |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
| A+B | 14 |
Шаг 3: Повторяем шаг 2 до тех пор, пока не останется только один узел:
| Символ/Узел | Вес |
|---|---|
| A | 5 |
| B | 9 |
| C | 12 |
| D | 13 |
| E | 16 |
| F | 45 |
| A+B | 14 |
| A+B+C | 26 |
| A+B+C+D | 39 |
| A+B+C+D+E | 55 |
| A+B+C+D+E+F | 100 |
Шаг 4: Построение кодов Хаффмана для каждого символа. Начнем с корня дерева и будем двигаться по ребрам влево для кода 0 и вправо для кода 1:
A: 0
B: 10
C: 11
D: 100
E: 101
F: 11
Теперь мы имеем построенное дерево Хаффмана и соответствующие коды для каждого символа. Этот алгоритм позволяет эффективно сжимать данные, используя наименьшее количество бит для наиболее часто встречающихся символов.