Дерево кодирования
Дерево кодирования — это схема, которая показывает, как символам сопоставляются двоичные последовательности и как по этим последовательностям восстановить исходное сообщение. По ветвям дерева удобно выполнять и кодирование и декодирование.
Как читать дерево
Чтобы найти код символа, начинают в корне и идут к его вершине, выписывая метки пройденных ветвей. Чтобы декодировать сообщение, читают биты слева направо и двигаются по дереву: 0 — по ветви с меткой 0, 1 — по ветви с меткой 1. Достигнув конечной вершины, записывают найденный символ и возвращаются в корень для следующего фрагмента.
Если каждый символ расположен только в конечной вершине, полученный набор кодов является префиксным кодом: код одного символа не начинается с кода другого. Поэтому сообщение можно читать однозначно, не используя разделители.
Пусть из корня ветвь 0 ведёт к символу А, а ветви 1 затем 0 и 1 ведут к символам Б и В. Тогда А имеет код \(0\), Б — \(10\), В — \(11\). Последовательность \(01011\) читается так: \(0\to А\), затем \(10\to Б\), затем \(11\to В\). Результат: АБВ.
Дерево кодирования не обязано быть двоичным: у вершины может быть и другое число ветвей. Двоичное дерево используют именно тогда, когда ветви обозначают 0 и 1. Кроме того, дерево задаёт способ чтения кодов, но само по себе не определяет частоты символов или степень сжатия.
Какой путь соответствует коду символа 101?
Главное
- Код символа — последовательность меток ветвей на пути от корня к его конечной вершине.
- При декодировании биты читают слева направо; после конечной вершины возвращаются в корень.
- В префиксном коде конечные вершины не являются предками друг друга, поэтому сообщение декодируется однозначно.