Для определения кодов, сначала определяются частоты появления символов в сообщении, и составляется таблица частот появления символов(или таблица вероятностей появления символов, иногда используют готовую таблицу).
Определяется сколько раз символ появляется в сообщении:
- Символ "О" появляется 6 раз
- Символ "Т" появляется 6 раз
- Символ "_" появляется раз
- Символ "П" появляется 5 раз
- Символ "А" появляется 1 раз
- Символ "К" появляется 1 раз
- Символ "Ы" появляется 2 раза
- Символ "Л" появляется 3 раза
- Символ "Ь" появляется 1 раз
- Символ "Ю" появляется 1 раз
- Символ "Е" появляется 1 раз
- Символ "И" появляется 1 раз
Далее создаётся список символов в порядке возрастания частоты повторений символов
- "А"(1)
- "К"(1)
- "Ь"(1)
- "Ю"(1)
- "Е"(1)
- "И"(1)
- "Ы"(2)
- "Л"(3)
- "П"(5)
- "О"(6)
- "Т"(6)
- "_"(6)
Для определения кодов символов строим орграф (двоичное дерево),
Создаётся список нераспределённых узлов, каждому узлу назначается вес, равный частоте появления символа - указан в скобках.
Два верхних узла объединяются в новый узел с весом, равным сумме их весов, и этот узел добавляется в список нераспределенных узлов в соответствии с весом этого узла, а исходные узлы удаляются, таким образом на каждом шаге список становится короче на один элемент.
Этот процесс повторяется до тех пор пока не останется один корневой узел.
после первого шага (символы А и К объединяются в узел 1) получится список:
- "Ь"(1)
- "Ю"(1)
- "Е"(1)
- "И"(1)
- 1 (2)
- "Ы"(2)
- "Л"(3)
- "П"(5)
- "О"(6)
- "Т"(6)
- "_"(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+<wbr />1*5+2*4+3*3+1*5+1*5+1<wbr />*5+1*5=110 бит
Код сообщения выглядит так:
11011100111110101110<wbr />111011000001101110101<wbr />011111100101011101010<wbr />010001011100010111001<wbr />010011000101000011110<wbr />001111
Длина исходного сообщения 34 байт или 272 бит в ASCII:
сообщение содержит 12 различных символов. Длина кода одного символа при равномерном кодировании равна log₂(12)=4 бит
при равномерном кодировании длина текста равна 34*4=136 бит
коэффициэнт сжатия по отношению к восьмибитному коду(например ASCII) равен 272/110=~2.47
коэффициэнт сжатия по отношению к юникоду равен 544/110=~4.94
коэффициэнт сжатия по отношению к равномерному коду равен 136/110=~1.24
