Конвенция для кодирования Хаффмана

Question

Есть ли соглашение для генерации кодировки Хаффмана для определенного алфавита? Кажется, что результирующая кодировка зависит как от того, присваиваете ли вы «0» левому ребенку или правому ребенку, так и по тому, как вы определяете, какой символ пойдет в левое дерево.

Wikipedia говорит, что:

В общей конвенции, бит «0» означает следующее левого ребенка и бит «1» означает следующее правом ребенка.

Так что это ответ на первую половину дисперсии. Тем не менее, я не мог найти никакого соглашения во второй половине. Я бы предположил, что что-то вроде того, что узел с меньшей вероятностью идет слева, но несколько примеров деревьев Хаффмана онлайн не делают этого.

Например:

Так есть соглашение о присвоении узлов слева и справа, или это зависит от реализации?

Прошу прощения, если это дубликат, но я не смог найти ответ.

Answer 1

Да, на самом деле есть. Не столько соглашение об интероперабельности, сколько эффективность кодирования. Он называется Canonical Huffman, где коды назначаются в численном порядке от кратчайших кодов до самых длинных кодов и в пределах одной длины кода они назначаются в лексикографическом порядке на символах. Это позволяет передавать только длину кода для каждого символа, в отличие от всей древовидной структуры.

Как правило, используется дерево алгоритмов Хаффмана только для определения количества бит для каждого символа. Затем дерево отбрасывается. Битовые значения никогда не назначаются ветвям. Затем коды строятся непосредственно из длин, используя порядок выше.