Как алгоритмом Хаффмана сжать фразу от топота копыт пыль летит?

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

Определяется сколько раз символ появляется в сообщении:

1. Символ "О" появляется 6 раз
2. Символ "Т" появляется 6 раз
3. Символ "_" появляется раз
4. Символ "П" появляется 5 раз
5. Символ "А" появляется 1 раз
6. Символ "К" появляется 1 раз
7. Символ "Ы" появляется 2 раза
8. Символ "Л" появляется 3 раза
9. Символ "Ь" появляется 1 раз
10. Символ "Ю" появляется 1 раз
11. Символ "Е" появляется 1 раз
12. Символ "И" появляется 1 раз

Далее создаётся список символов в порядке возрастания частоты повторений символов

1. "А"(1)
2. "К"(1)
3. "Ь"(1)
4. "Ю"(1)
5. "Е"(1)
6. "И"(1)
7. "Ы"(2)
8. "Л"(3)
9. "П"(5)
10. "О"(6)
11. "Т"(6)
12. "_"(6)

Для определения кодов символов строим орграф (двоичное дерево),

Создаётся список нераспределённых узлов, каждому узлу назначается вес, равный частоте появления символа - указан в скобках.

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

Этот процесс повторяется до тех пор пока не останется один корневой узел.

после первого шага (символы А и К объединяются в узел 1) получится список:

1. "Ь"(1)
2. "Ю"(1)
3. "Е"(1)
4. "И"(1)
5. 1 (2)
6. "Ы"(2)
7. "Л"(3)
8. "П"(5)
9. "О"(6)
10. "Т"(6)
11. "_"(6)

повторяем операцию пока не останется только один узел 11 с весом 34

строим дерево: левое ребро соответствует коду 0 а правое коду 1

Путь по дереву от корня к конечным элементам (листьям) создаёт код элемента

Символ "_" имеет код 00

Символ "Т" имеет код 111

Символ "О" имеет код 110

Символ "П" имеет код 101

Символ "Л" имеет код 010

Символ "Ы" имеет код 0111

Символ "И" имеет код 10001

Символ "Е" имеет код 10000

Символ "Ю" имеет код 10011

Символ "Ь" имеет код 10010

Символ "К" имеет код 01101

Символ "А" имеет код 01100

Все коды префиксные - ни один символ не является началом другого символа, и самые частые символы имеют наименьшую длину.

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода: 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 бит

Код сообщения выглядит так:

11011100111110101110­111011000001101110101­011111100101011101010­010001011100010111001­010011000101000011110­001111

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

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

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

коэффициэнт сжатия по отношению к восьмибитному коду(например ASCII) равен 272/110=~2.47

коэффициэнт сжатия по отношению к юникоду равен 544/110=~4.94

коэффициэнт сжатия по отношению к равномерному коду равен 136/110=~1.24