Записываем фразу:
КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ
считаем количество появлений символов:
- Символ "К" встречается 8 раз
- Символ "А" встречается 11 раз
- Символ "Р" встречается 8 раз
- Символ "Л" встречается 9 раз
- Символ " " встречается 9 раз
- Символ "У" встречается 4 раза
- Символ "Ы" встречается 2 раза
- Символ "О" встречается 1 раз
- Символ "," встречается раз
- Символ "Н" встречается 1 раз
- Символ "Е" встречается 1 раз
- Символ "Т" встречается 1 раз
Сортируем и получаем список нераспределенных узлов
- {"О" (1)}
- {"," (1)}
- {"Н" (1)}
- {"Е" (1)}
- {"Т" (1)}
- {"Ы" (2)}
- {"У" (4)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {"О" (1)} и {"," (1)} в узел {1 (2)} и добавляем в список вместо этих узлов с учетом веса.
- {"Н" (1)}
- {"Е" (1)}
- {"Т" (1)}
- {1 (2)}
- {"Ы" (2)}
- {"У" (4)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {"Н" (1)} и {"Е" (1)} в узел {2 (2)} и повторяем добавление в список.
- {"Т" (1)}
- {2 (2)}
- {1 (2)}
- {"Ы" (2)}
- {"У" (4)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {"Т" (1)} и {2 (2)} в узел {3 (3)} и повторяем добавление в список.
- {1 (2)}
- {"Ы" (2)}
- {3 (3)}
- {"У" (4)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {1 (2)} и {"Ы" (2)} в узел {4 (4)} и повторяем добавление в список.
- {3 (3)}
- {4 (4)}
- {"У" (4)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {3 (3)} и {4 (4)} в узел {5 (7)} и повторяем добавление в список.
- {"У" (4)}
- {5 (7)}
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {"А" (11)}
Объединяем {"У" (4)} и {5 (7)} в узел {6 (11)} и повторяем добавление в список.
- {"К" (8)}
- {"Р" (8)}
- {"Л" (9)}
- {" " (9)}
- {6 (11)}
- {"А" (11)}
Объединяем {"К" (8)} и {"Р" (8)} в узел {7 (16)} и повторяем добавление в список.
- {"Л" (9)}
- {" " (9)}
- {6 (11)}
- {"А" (11)}
- {7 (16)}
Объединяем {"Л" (9)} и {" " (9)} в узел {8 (18)} и повторяем добавление в список.
- {6 (11)}
- {"А" (11)}
- {7 (16)}
- {8 (18)}
Объединяем {6 (11)} и {"А" (11)} в узел {9 (22)} и повторяем добавление в список.
- {7 (16)}
- {8 (18)}
- {9 (22)}
Объединяем {7 (16)} и {8 (18)} в узел {10 (34)} и повторяем добавление в список.
- {9 (22)}
- {10 (34)}
Объединяем {9 (22)} и {10 (34)} в корневой узел {11 (56)} и дерево готово.
Графическое изображение дерева строим начиная с корневого узла, в который входят узлы {9 (10)} и {10 (34)}
Каждый узел изображаем в виде прямоугольника из которого выходят 2 ребра ведущие к входящим в него узлам.
Левому ребру соответствует код 0, а правому код 1
Концевые узлы (листья дерева), содержащие символы текста, выделяем цветом.
Графически двоичное дерево кодов выглядит так:
по построенному дереву определяем коды символов как путь от корня до листа (концевого узла)
- "А" код символа 01
- " " код символа 111
- "Л" код символа 110
- "Р" код символа 101
- "К" код символа 100
- "У" код символа 000
- "Ы" код символа 00111
- "Т" код символа 00100
- "Е" код символа 001011
- "Н" код символа 001010
- "," код символа 001101
- "О" код символа 001100
Длина кодированного сообщения равна сумме произведений количества повторений каждого символа на длину его кода:
8*3+11*2+8*3+9*3+9*3<wbr />+4*3+2*5+1*6+1*6+1*6+<wbr />1*6+1*5=175 бит
Длина кодированного сообщения равна 175 бит:
10001101110111000100<wbr />101011101110001111001<wbr />100110100111111100001<wbr />100101011101100011100<wbr />1101
11110011001101011110<wbr />001001010111001111000<wbr />111100011011100111110<wbr />011001101001010001011<wbr />00100
Анализ сжатия фразы КАРЛ УКРАЛ У КЛАРЫ КОРАЛЛЫ, КЛАРА УКРАЛА У КАРЛА КЛАРНЕТ
Длина исходного сообщения 56 байт или 448 бит в ASCII:
сообщение содержит 12 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит
при равномерном кодировании минимальной длинны, длинна текста равна 56*4=224 бит
Коэффициэнт сжатия к восьмибитному коду K=448/175=2.56
Коэффициэнт сжатия к равномерному коду минимальной длинны K=224/175=1.28