1.4.2. Средняя длина кода

На рис. 1.13а представлено множество из пяти символов с их вероятностями, а также типичное дерево Хаффмана. Символ А возникает в 55% случаев и ему присваивается однобитовый код, что вносит вклад в  в среднюю длину. Символ Е возникает лишь в 2% случаев. Ему присваивается код длины 4, и его вклад равен . Тогда средняя длина кода равна  бит на символ.

Удивительно, но тот же результат получится, если сложить значения вероятностей четырех внутренних узлов кодового дерева: . Это наблюдение дает простой способ вычисления средней длины для кодов Хаффмана без использования операции умножения. Надо просто сложить значения внутренних узлов дерева. Табл. 1.11 иллюстрирует, почему этот метод будет работать.

0.05 =		= 0.02 + 0.03
0.20 =	0.05 + 0.15	= 0.02 + 0.03 + 0.15
0.45 =	0.20 + 0.25	= 0.02 + 0.03 + 0.15 + 0.25
1.00 =	0.45 + 0.55	= 0.02 + 0.03 + 0.15 + 0.25 + 0.55

Табл. 1.11. Состав узлов.

(В таблице внутренние узлы выделены.) В левом столбце выписаны величины всех внутренних узлов. В правых столбцах показано, как величины складываются из величин предыдущих узлов и из величин листьев. Если сложить числа в левом столбце, то получится 1.7, а складывая числа в остальных столбцах, убеждаемся, что это число 1.7 есть сумма четырех 0.02, четырех 0.03, трех 0.15, двух 0.25 и одного 0.55.

Это рассуждение годится и в общем случае. Легко видеть, что в дереве типа Хаффмана (т.е., дереве, в котором каждый узел есть сумма своих потомков) взвешенная сумма листьев, где вес листа - это его расстояние до корня, равна сумме всех внутренних узлов. (Это свойство было мне сообщено Джоном Мотилом.)

0.05 =		= 0.02 + 0.03 + …
	0.05 + …	= 0.02 + 0.03 + …
		= 0.02 + 0.03 + …
		= 0.02 + 0.03 + …
1.0 =		= 0.02 + 0.03 + …

Табл. 1.12. Состав узлов.

На рис. 1.13b показано такое дерево, где предполагается, что два листа 0.02 и 0.03 имеют коды Хаффмана длины . Внутри дерева эти листья являются потомками внутреннего узла 0.05, который, в свою очередь, связан с корнем с помощью  внутренних узлов от  до . Табл. 1.12 состоит из  строк и показывает, что две величины 0.02 и 0.03 включаются в разные внутренние узлы ровно  раз. Сложение величин всех внутренних узлов дает вклад от этих двух листьев равный . Поскольку эти листья выбраны произвольно, ясно, что эта сумма включает в себя аналогичный вклад от всех остальных узлов, то есть, равна средней длине кода. Эта число также равно сумме левого столбца или сумме всех внутренних узлов, которая и определит среднюю длину кода.

Отметим, что в доказательстве нигде не предполагалось, что дерево - двоичное. Поэтому это свойство выполнено для любого дерева, в котором узлы являются суммой своих потомков.