Question

Постройте дерево Хаффмана для любых двух фраз из списка ниже:

1) Не руби дрова на траве двора.

2) Прецедент с претендентом.

3) Течёт речка, печёт печка.

Покажите полное решение.

Answer 1

Хорошо, давайте разберемся, как построить дерево Хаффмана для каждой из фраз.

Для начала, нам нужно подсчитать частоту появления каждого символа в каждой фразе. Затем мы создадим список символов и их частот, чтобы иметь информацию о том, какие символы нам нужно закодировать в дереве.

Давайте рассмотрим первую фразу "Не руби дрова на траве двора." и найдем частоты символов:

Символ | Частота
-------|---------
. | 2
а | 2
о | 2
е | 2
р | 2
н | 1
т | 1
и | 1
д | 1
в | 1
б | 1
у | 1
й | 1
. | 1
знак пробела | 5

Теперь создадим список символов и их частот:

Символ | Частота
-------|---------
знак пробела | 5
. | 2
а | 2
о | 2
е | 2
р | 2
н | 1
т | 1
и | 1
д | 1
в | 1
б | 1
у | 1
й | 1
. | 1

Теперь давайте начнем строить дерево. Начнем с символов, которые имеют наименьшую частоту, и объединим их:

0: знак пробела | 5
1: . | 2
2: а | 2
3: о | 2
4: е | 2
5: р | 2
6: н | 1
7: т | 1
8: и | 1
9: д | 1
10: в | 1
11: б | 1
12: у | 1
13: й | 1
14: . | 1

Теперь объединим два символа с наименьшей частотой (1 и 14):

0: знак пробела | 5
1: . | 2
2: а | 2
3: о | 2
4: е | 2
5: р | 2
6: н | 1
7: т | 1
8: и | 1
9: д | 1
10: в | 1
11: б | 1
12: у | 1
13: й | 1
2 : .(1+14) | 2

Теперь давайте объединим символы 6 и 13:

0: знак пробела | 5
1: . | 2
2: а | 2
3: о | 2
4: е | 2
5: р | 2
6 : н(6+13) | 2
7: т | 1
8: и | 1
9: д | 1
10: в | 1
11: б | 1
12: у | 1
6 : н(6+13)
13 : й | 1
2 : .(1+14) | 2

Продолжим этот процесс, объединив символы 7 и 8, а затем символы 9 и 10:

0: знак пробела | 5
1: . | 2
2: а | 2
3: о | 2
4: е | 2
5: р | 2
6 : н(6+13) | 2
7 : т(7+8) | 2
9 : д(9+10) | 2
11: б | 1
12: у | 1
13: й | 1
2 : .(1+14) | 2

Теперь объединим символы 11 и 12:

0: знак пробела | 5
1: . | 2
2: а | 2
3: о | 2
4: е | 2
5: р | 2
6 : н(6+13) | 2
7 : т(7+8) |2
9 : д(9+10) |2
11: б(11+12) | 2
13: й |1
2 : .(1+14) | 2

В результате мы получим окончательное дерево Хаффмана для данной фразы:

0: знак пробела (5)
/ \
1: . (2) \
/ \ \
3: о (2) 2: а (2)
/ \ / \
5: р(2) \ / \
/ 6: н(2) 4: е(2)
/ \ / \
13: й 11: б 9: д 7: т



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