Как найти коды Хаффмана для фразы Карл украл у Клары кораллы, . . .?

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

КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ

считаем количество появлений символов:

1. Символ "К" встречается 8 раз
2. Символ "А" встречается 11 раз
3. Символ "Р" встречается 8 раз
4. Символ "Л" встречается 9 раз
5. Символ " " встречается 9 раз
6. Символ "У" встречается 4 раза
7. Символ "Ы" встречается 2 раза
8. Символ "О" встречается 1 раз
9. Символ "," встречается раз
10. Символ "Н" встречается 1 раз
11. Символ "Е" встречается 1 раз
12. Символ "Т" встречается 1 раз

Сортируем и получаем список нераспределенных узлов

1. {"О" (1)}
2. {"," (1)}
3. {"Н" (1)}
4. {"Е" (1)}
5. {"Т" (1)}
6. {"Ы" (2)}
7. {"У" (4)}
8. {"К" (8)}
9. {"Р" (8)}
10. {"Л" (9)}
11. {" " (9)}
12. {"А" (11)}

Объединяем {"О" (1)} и {"," (1)} в узел {1 (2)} и добавляем в список вместо этих узлов с учетом веса.

1. {"Н" (1)}
2. {"Е" (1)}
3. {"Т" (1)}
4. {1 (2)}
5. {"Ы" (2)}
6. {"У" (4)}
7. {"К" (8)}
8. {"Р" (8)}
9. {"Л" (9)}
10. {" " (9)}
11. {"А" (11)}

Объединяем {"Н" (1)} и {"Е" (1)} в узел {2 (2)} и повторяем добавление в список.

1. {"Т" (1)}
2. {2 (2)}
3. {1 (2)}
4. {"Ы" (2)}
5. {"У" (4)}
6. {"К" (8)}
7. {"Р" (8)}
8. {"Л" (9)}
9. {" " (9)}
10. {"А" (11)}

Объединяем {"Т" (1)} и {2 (2)} в узел {3 (3)} и повторяем добавление в список.

1. {1 (2)}
2. {"Ы" (2)}
3. {3 (3)}
4. {"У" (4)}
5. {"К" (8)}
6. {"Р" (8)}
7. {"Л" (9)}
8. {" " (9)}
9. {"А" (11)}

Объединяем {1 (2)} и {"Ы" (2)} в узел {4 (4)} и повторяем добавление в список.

1. {3 (3)}
2. {4 (4)}
3. {"У" (4)}
4. {"К" (8)}
5. {"Р" (8)}
6. {"Л" (9)}
7. {" " (9)}
8. {"А" (11)}

Объединяем {3 (3)} и {4 (4)} в узел {5 (7)} и повторяем добавление в список.

1. {"У" (4)}
2. {5 (7)}
3. {"К" (8)}
4. {"Р" (8)}
5. {"Л" (9)}
6. {" " (9)}
7. {"А" (11)}

Объединяем {"У" (4)} и {5 (7)} в узел {6 (11)} и повторяем добавление в список.

1. {"К" (8)}
2. {"Р" (8)}
3. {"Л" (9)}
4. {" " (9)}
5. {6 (11)}
6. {"А" (11)}

Объединяем {"К" (8)} и {"Р" (8)} в узел {7 (16)} и повторяем добавление в список.

1. {"Л" (9)}
2. {" " (9)}
3. {6 (11)}
4. {"А" (11)}
5. {7 (16)}

Объединяем {"Л" (9)} и {" " (9)} в узел {8 (18)} и повторяем добавление в список.

1. {6 (11)}
2. {"А" (11)}
3. {7 (16)}
4. {8 (18)}

Объединяем {6 (11)} и {"А" (11)} в узел {9 (22)} и повторяем добавление в список.

1. {7 (16)}
2. {8 (18)}
3. {9 (22)}

Объединяем {7 (16)} и {8 (18)} в узел {10 (34)} и повторяем добавление в список.

1. {9 (22)}
2. {10 (34)}

Объединяем {9 (22)} и {10 (34)} в корневой узел {11 (56)} и дерево готово.

Графическое изображение дерева строим начиная с корневого узла, в который входят узлы {9 (10)} и {10 (34)}

Каждый узел изображаем в виде прямоугольника из которого выходят 2 ребра ведущие к входящим в него узлам.

Левому ребру соответствует код 0, а правому код 1

Концевые узлы (листья дерева), содержащие символы текста, выделяем цветом.

Графически двоичное дерево кодов выглядит так:

по построенному дереву определяем коды символов как путь от корня до листа (концевого узла)

1. "А" код символа 01
2. " " код символа 111
3. "Л" код символа 110
4. "Р" код символа 101
5. "К" код символа 100
6. "У" код символа 000
7. "Ы" код символа 00111
8. "Т" код символа 00100
9. "Е" код символа 001011
10. "Н" код символа 001010
11. "," код символа 001101
12. "О" код символа 001100

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

8*3+11*2+8*3+9*3+9*3­+4*3+2*5+1*6+1*6+1*6+­1*6+1*5=175 бит

Длина кодированного сообщения равна 175 бит:

10001101110111000100­101011101110001111001­100110100111111100001­100101011101100011100­1101

11110011001101011110­001001010111001111000­111100011011100111110­011001101001010001011­00100

Анализ сжатия фразы КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ

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

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

при равномерном кодировании минимальной длинны, длинна текста равна 56*4=224 бит

Коэффициэнт сжатия к восьмибитному коду K=448/175=2.56

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