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

Строим двоичное дерево кодов динамически, по частоте появления каждого символа в сообщении (можно и по готовой таблице вероятностей появления символов).

Определим частоты появления символов

1. Символ "Ш" встречается 4 раза
2. Символ "Л" встречается 2 раза
3. Символ "А" встречается 5 раз
4. Символ " " встречается 6 раз
5. Символ "С" встречается 6 раз
6. Символ "П" встречается 1 раз
7. Символ "О" встречается 3 раза
8. Символ "Е" встречается 1 раз
9. Символ "И" встречается 1 раз
10. Символ "У" встречается 2 раз
11. Символ "К" встречается 1 раз

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

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

1. "П" (1)
2. "Е" (1)
3. "И" (1)
4. "К" (1)
5. "Л" (2)
6. "У" (2)
7. "О" (3)
8. "Ш" (4)
9. "А" (5)
10. "_" (6)
11. "С" (6)

объединяем узлы с минимальными весами в один родительский узел с суммарным весом

и помещаем его в список вместо этих узлов в соответствии с весом этого узла

в результате список нераспределённых узлов сокращается на 1 узел.

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

Узлы "П" и "Е" объединяем в узел 1

после первого шага список примет вид:

1. "И" (1)
2. "К" (1)
3. 1 (2)
4. "Л" (2)
5. "У" (2)
6. "О" (3)
7. "Ш" (4)
8. "А" (5)
9. "_" (6)
10. "С" (6)

после шага 10 останется один корневой узел с весом 32

строим кодовое дерево: узел с меньшим весом помещаем в левую ветвь, а с большим в правую.

При обходе дерева левое ребро добавляет к коду бит 0, а правое бит 1

получаем следующую таблицу кодов символов

1. Код символа "С" равен 00
2. Код символа " " равен 111
3. Код символа "А" равен 110
4. Код символа "Ш" равен 101
5. Код символа "О" равен 010
6. Код символа "У" равен 0111
7. Код символа "Л" равен 0110
8. Код символа "К" равен 10001
9. Код символа "И" равен 10000
10. Код символа "Е" равен 10011
11. Код символа "П" равен 10010

Заметим , что получились префиксные коды: код любого символа не является началом кода другого символа, т.е. соблюдается условие Фано.

Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:

4*3+2*4+5*3+6*3+6*2+­1*5+3*3+1*5+1*5+2*4+1­*5=102 бит

Кодирование осуществляется по таблице кодов, заменой каждого символа его кодом

Кодированное сообщение имеет вид:

10101101101110011010­111011110010010111101­010000010011111100001­110001000110011011011­1000111101100010111

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

Фраза "ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ" имеет длину 32 байт или 256 бит в восьмибитном коде (например ASCII) или 512 бит в юникоде.

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

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

Коэффициент сжатия по сравнению с равномерным кодированием равен 128/102=~1,25

Коэффициент сжатия по сравнению с кодом ASCII кодированием равен 256/102=~2,5

Коэффициент сжатия по сравнению с кодированием в юникоде равен 512/102=~5