Я знал, что дерево Хаффмана - это дерево, используемое для оптимального префиксного кода, но есть ли какое-нибудь дерево для оптимального префиксного кода , кроме дерева Хаффмана? Если есть такие деревья, будут ли их высоты одинаковыми? Большое спасибо!Есть ли дерево для оптимального префиксного кода, кроме дерева Хаффмана? Будет ли высота такой же, как высота дерева Хаффмана?
Деревья Хаффмана построены рекурсивно, взяв два в настоящее время наименьших вероятностных символа и объединив их.
Если есть другие символы с одинаковой низкой вероятностью, тогда эти символы могут быть объединены.
Это означает, что окончательное дерево не определено однозначно и существует несколько оптимальных кодов префикса с потенциально разной высотой.
Для примера рассмотрим символы и вероятности ниже:
A 1/3
B 1/3
C 1/6
D 1/6
Может быть закодирован как:
A 0
B 10
C 110
D 111
или
A 00
B 01
C 10
D 11
Оба кодировок имеют ожидаемое число битов в символ равен 2, но разные высоты.
Однако все оптимальные префиксные коды могут быть построены алгоритмом Хаффмана для подходящего выбора порядка по связям с вероятностями.
В пределах ограничений проблемы кода Хаффмана, то есть представления каждого символа с помощью префикс-уникальной последовательности бит, тогда существует ровно одно оптимальное общее количество бит, которое может быть достигнуто, и алгоритм Хаффмана достигает этого. Существуют и другие подходы, которые приходят к одному и тому же ответу.
Как заметил Петр де Риваз, в некоторых особых случаях алгоритм Хаффмана имеет несколько вариантов на некоторых этапах, в которых из двух минимальных вероятностей набора кодов выбирается, что может привести к разным деревьям. Таким образом, дерево высота/глубина вы упоминаете не уникально, но общее количество бит (сумма бит длины каждого символа, взвешенного по его вероятности) всегда одно и то же.