Записываем фразу:

ОТ ТОПОТА КОПЫТ ПЫЛЬ ПО ПОЛЮ ЛЕТИТ

считаем количество появлений (вес) символов в сообщении и записываем список символов:

Символ "О" встречается 6 раз

Символ "Т" встречается 6 раз

Символ " " встречается 6 раз

Символ "П" встречается 5 раз

Символ "А" встречается 1 раз

Символ "К" встречается 1 раз

Символ "Ы" встречается 2 раза

Символ "Л" встречается 3 раза

Символ "Ь" встречается 1 раз

Символ "Ю" встречается 1 раз

Символ "Е" встречается 1 раз

Символ "И" встречается 1 раз

Включаем все символы в список нераспределённых узлов в порядке возрастания веса символа:

{"А"(1)}

{"К"(1)}

{"Ь"(1)}

{"Ю"(1)}

{"Е"(1)}

{"И"(1)}

{"Ы"(2)}

{"Л"(3)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 1

Объединяем {"А"(1)}+{"К"(1)} в узел {1 (2)}

{"Ь"(1)}

{"Ю"(1)}

{"Е"(1)}

{"И"(1)}

{"Ы"(2)}

{1(2)}

{"Л"(3)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 2

Объединяем {"Ь"(1)}+{"Ю"(1)} в узел {2 (2)}

{"Е"(1)}

{"И"(1)}

{"Ы"(2)}

{1(2)}

{2(2)}

{"Л"(3)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 3

Объединяем {"Е"(1)}+{"И"(1)} в узел {3 (2)}

{"Ы"(2)}

{1(2)}

{2(2)}

{3(2)}

{"Л"(3)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 4

Объединяем {"Ы"(2)}+{1(2)} в узел {4 (4)}

{2(2)}

{3(2)}

{"Л"(3)}

{4(4)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 5

Объединяем {2(2)}+{3(2)} в узел {5 (4)}

{"Л"(3)}

{4(4)}

{5(4)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

Шаг 6

Объединяем {"Л"(3)}+{4(4)} в узел {6 (7)}

{5(4)}

{"П"(5)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

{6(7)}

Шаг 7

Объединяем {5(4)}+{"П"(5)} в узел {7 (9)}

{"О"(6)}

{"Т"(6)}

{" "(6)}

{6(7)}

{7(9)}

Шаг 8

Объединяем {"О"(6)}+{"Т"(6)} в узел {8 (12)}

{" "(6)}

{6(7)}

{7(9)}

{8(12)}

Шаг 9

Объединяем {" "(6)}+{6(7)} в узел {9 (13)}

{7(9)}

{8(12)}

{9(13)}

Шаг 10

Объединяем {7(9)}+{8(12)} в узел {10 (21)}

{9(13)}

{10(21)}

Шаг 11

Объединяем {9(13)}+{10(21)} в узел {11 (34)}

Это последний (корневой) узел.

По полученным узлам строим дерево, начиная с корневого узла:

Коды символов считаем как пути от корня дерева до листа (конечного узла), соответствующего символу:

1. Код символа " " равен 00
2. Код символа "Т" равен 111
3. Код символа "О" равен 110
4. Код символа "П" равен 101
5. Код символа "Л" равен 010
6. Код символа "Ы" равен 0110
7. Код символа "И" равен 10011
8. Код символа "Е" равен 10010
9. Код символа "Ю" равен 10001
10. Код символа "Ь" равен 10000
11. Код символа "К" равен 01111
12. Код символа "А" равен 01110

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода: 6*3+6*3+6*2+5*3+1*5+1*5+2*4+3*3+1*5+1*5+1*5+1*5=110 бит

Кодированное сообщение длиной 110 бит

Характеристики сжатия фразы ОТ ТОПОТА КОПЫТ ПЫЛЬ ПО ПОЛЮ ЛЕТИТ

Длина исходного сообщения 34 байт или 272 бит в ASCII:

сообщение содержит 12 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит

при равномерном кодировании длина текста равна 34*4=136 бит

Коэффициент сжатия к восьмибитному коду K= 272/110=2.4727272727272727

Коэффициент сжатия к равномерному коду минимальной длины K=136/110=1.2363636363636363