Соглашение о кодировании Хаффмана

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

Википедия говорит, что:

По общему соглашению, бит «0» означает следование за левым дочерним элементом, а бит «1» — за правым дочерним элементом.

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

Например:

дерево Хаффмана

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

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


huffman-code
person andars    schedule 16.11.2015    source источник
comment
Я думаю, что единственное соглашение заключается в алгоритмах, которые мы выбрали в качестве стандартных, то есть gzip.   -  person Jonathon Reinhart    schedule 16.11.2015
comment
В таком случае это имеет значение? Будет ли когда-нибудь случай, когда выбор одного приведет к менее эффективному коду, чем выбор другого? (возможно, это должен быть новый вопрос)   -  person andars    schedule 16.11.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

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

person Mark Adler    schedule 16.11.2015
comment
Имеет смысл. Спасибо - person andars; 16.11.2015