Когда я впервые услышал о дереве Хаффмана, я был удивлен, насколько эффективным может быть данный метод сжатия данных. Решив опробовать его на практике, я решил построить дерево Хаффмана для фразы ″Шла Саша по шоссе″.Сначала я составил частотный словарь для всех символов в данной фразе. В результате получился следующий список⁚
— Ш⁚ 2 раза
— л⁚ 1 раз
— а⁚ 2 раза
— С⁚ 1 раз
— ш⁚ 2 раза
— о⁚ 1 раз
— с⁚ 1 раз
— е⁚ 1 раз
Затем я создал список узлов, каждый из которых представлял собой символ и его частоту. Затем я отсортировал этот список по возрастанию частоты. Вид списка после сортировки⁚
1. С⁚ 1
2. е⁚ 1
3. л⁚ 1
4. о⁚ 1
5. с⁚ 1
6. ш⁚ 2
7. а⁚ 2
8. Ш⁚ 2
Далее начался этап построения дерева Хаффмана. Я последовательно объединял две наименее частотных вершины и создавал новый узел с их суммарной частотой. Затем этот новый узел добавлялся в список узлов, а старые узлы удалялись. Процесс продолжался до тех пор, пока список узлов не сократился до одной вершины.Вот последовательность объединения узлов, которую я получил⁚
1. объединяем С (1) и е (1), получаем новый узел Се (2)
2. объединяем л (1) и о (1), получаем новый узел ло (2)
3. объединяем с (1) и ш (2)٫ получаем новый узел сш (3)
4. объединяем ло (2) и и сш (3), получаем новый узел лош (5)
5. объединяем ш (2) и а (2), получаем новый узел ша (4)
6. объединяем лош (5) и ша (4), получаем новый узел лоша (9)
7. объединяем лоша (9) и Ш (2), получаем новый узел лошаШ (11)
- лошаШ (11)
- ло (2)
- ша (4)
- ш (2)
- а (2)
- Се (2)
- С (1)
- е (1)
Когда дерево Хаффмана построено, можно найти кодовые слова для каждого символа, следуя пути от корня до каждого символа. В моем случае, кодовые слова получились следующие⁚
— Ш⁚ 0
— л⁚ 100
— а⁚ 101
— С⁚ 110
— ш⁚ 111
— о⁚ 010
— с⁚ 011
— е⁚ 001
Итак, построив дерево Хаффмана для фразы ″Шла Саша по шоссе″, я получил оптимальный способ сжатия информации, где более частые символы имеют более короткие кодовые слова. Этот метод может быть очень полезным для сжатия больших объемов данных и эффективного хранения информации.