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

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

ШВЕИ САМИ СШИЛИ ШУБУ ИЗ ШИНШИЛЛЫ

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

Символ "Ш" Количество повторов в тексте 5

Символ "В" Количество повторов в тексте 1

Символ "Е" Количество повторов в тексте 1

Символ "И" Количество повторов в тексте 7

Символ " " Количество повторов в тексте 5

Символ "С" Количество повторов в тексте 2

Символ "А" Количество повторов в тексте 1

Символ "М" Количество повторов в тексте 1

Символ "Л" Количество повторов в тексте 3

Символ "У" Количество повторов в тексте 2

Символ "Б" Количество повторов в тексте 1

Символ "З" Количество повторов в тексте 1

Символ "Н" Количество повторов в тексте 1

Символ "Ы" Количество повторов в тексте 1

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

1. {"В" (1)}
2. {"Е" (1)}
3. {"А" (1)}
4. {"М" (1)}
5. {"Б" (1)}
6. {"З" (1)}
7. {"Н" (1)}
8. {"Ы" (1)}
9. {"С" (2)}
10. {"У" (2)}
11. {"Л" (3)}
12. {"Ш" (5)}
13. {" " (5)}
14. {"И" (7)}

Объединяем {"В" (1)} и {"Е" (1)}

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

1. {"А" (1)}
2. {"М" (1)}
3. {"Б" (1)}
4. {"З" (1)}
5. {"Н" (1)}
6. {"Ы" (1)}
7. {1 (2)}
8. {"С" (2)}
9. {"У" (2)}
10. {"Л" (3)}
11. {"Ш" (5)}
12. {" " (5)}
13. {"И" (7)}

Объединяем {"А" (1)} и {"М" (1)}

получаем узел {2 (2)} и добавляем в список вместо этих узлов

1. {"Б" (1)}
2. {"З" (1)}
3. {"Н" (1)}
4. {"Ы" (1)}
5. {2 (2)}
6. {1 (2)}
7. {"С" (2)}
8. {"У" (2)}
9. {"Л" (3)}
10. {"Ш" (5)}
11. {" " (5)}
12. {"И" (7)}

Объединяем {"Б" (1)} и {"З" (1)}

получаем узел {3 (2)} и добавляем в список вместо этих узлов

1. {"Н" (1)}
2. {"Ы" (1)}
3. {3 (2)}
4. {2 (2)}
5. {1 (2)}
6. {"С" (2)}
7. {"У" (2)}
8. {"Л" (3)}
9. {"Ш" (5)}
10. {" " (5)}
11. {"И" (7)}

Объединяем {"Н" (1)} и {"Ы" (1)}

получаем узел {4 (2)} и добавляем в список вместо этих узлов

1. {4 (2)}
2. {3 (2)}
3. {2 (2)}
4. {1 (2)}
5. {"С" (2)}
6. {"У" (2)}
7. {"Л" (3)}
8. {"Ш" (5)}
9. {" " (5)}
10. {"И" (7)}

Объединяем {4 (2)} и {3 (2)}

получаем узел {5 (4)} и добавляем в список вместо этих узлов

1. {2 (2)}
2. {1 (2)}
3. {"С" (2)}
4. {"У" (2)}
5. {"Л" (3)}
6. {5 (4)}
7. {"Ш" (5)}
8. {" " (5)}
9. {"И" (7)}

Объединяем {2 (2)} и {1 (2)}

получаем узел {6 (4)} и добавляем в список вместо этих узлов

1. {"С" (2)}
2. {"У" (2)}
3. {"Л" (3)}
4. {6 (4)}
5. {5 (4)}
6. {"Ш" (5)}
7. {" " (5)}
8. {"И" (7)}

Объединяем {"С" (2)} и {"У" (2)}

получаем узел {7 (4)} и добавляем в список вместо этих узлов

1. {"Л" (3)}
2. {7 (4)}
3. {6 (4)}
4. {5 (4)}
5. {"Ш" (5)}
6. {" " (5)}
7. {"И" (7)}

Объединяем {"Л" (3)} и {7 (4)}

получаем узел {8 (7)} и добавляем в список вместо этих узлов

1. {6 (4)}
2. {5 (4)}
3. {"Ш" (5)}
4. {" " (5)}
5. {8 (7)}
6. {"И" (7)}

Объединяем {6 (4)} и {5 (4)}

получаем узел {9 (8)} и добавляем в список вместо этих узлов

1. {"Ш" (5)}
2. {" " (5)}
3. {8 (7)}
4. {"И" (7)}
5. {9 (8)}

Объединяем {"Ш" (5)} и {" " (5)}

получаем узел {10 (10)} и добавляем в список вместо этих узлов

1. {8 (7)}
2. {"И" (7)}
3. {9 (8)}
4. {10 (10)}

Объединяем {8 (7)} и {"И" (7)}

получаем узел {11 (14)} и добавляем в список вместо этих узлов

1. {9 (8)}
2. {10 (10)}
3. {11 (14)}

Объединяем {9 (8)} и {10 (10)}

получаем узел {12 (18)} и добавляем в список вместо этих узлов

1. {11 (14)}
2. {12 (18)}

Узлы 11 и 12 объединяем в корневой узел {13 (32)}и дерево готово.

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

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

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

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

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

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

1. Символ "И" код равен 01
2. Символ " " код равен 111
3. Символ "Ш" код равен 110
4. Символ "Л" код равен 000
5. Символ "У" код равен 0011
6. Символ "С" код равен 0010
7. Символ "Ы" код равен 10101
8. Символ "Н" код равен 10100
9. Символ "З" код равен 10111
10. Символ "Б" код равен 10110
11. Символ "М" код равен 10001
12. Символ "А" код равен 10000
13. Символ "Е" код равен 10011
14. Символ "В" код равен 10010

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

5*3+1*5+1*5+7*2+5*3+­2*4+1*5+1*5+3*3+2*4+1­*5+1*5+1*5+1*5=109 бит

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

11010010100110111100­101000010001011110010­110010000111111000111­011000111110110111111­110011010011001000000­10101

ШВЕИ САМИ СШИЛИ ШУБУ ИЗ ШИНШИЛЛЫ

Длина исходного сообщения 32 байт или 256 бит в восьмибитном коде

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

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

Коэффициэнт сжатия к восьмибитному коду K=256/109=~2.35

Коэффициэнт сжатия к равномерному коду минимальной длинны K=128/109=~1.17