Изменения

|statement=Пусть <tex>C</tex> — алфавит, каждый символ <tex>c \in C</tex> которого встречается с частотой <tex>f[c]</tex>. Пусть <tex>x</tex> и <tex>y</tex> — два символа алфавита <tex>C</tex> с самыми низкими частотами.  Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую длину и отличаются лишь последним битом. |proof=Идея доказательства состоит в том, чтобы взять дерево <tex>T</tex>, представляющее произвольный оптимальный префиксный код, и преобразовать его в дерево, представляющее другой оптимальный префиксный код, в котором символы <tex>x</tex> и <tex>y</tex> являются листьями с общим родительским узлом, причем в новом дереве эти листья находятся на максимальной глубине.  Пусть <tex>a</tex> и <tex>b</tex> — два символа, представленные листьями с общим родительским узлом, которые находятся на максимальной глубине дерева <tex>T</tex>. Предположим без потери общности, что <tex>f[a] \le f[b]</tex> и <tex>f[x] \le f[y]</tex>. Поскольку <tex>f[x]</tex> и <tex>f[y]</tex> — две самые маленькие частоты (в указанном порядке), <tex>f[a]</tex> и <tex>f[b]</tex> — две произвольные частоты, то выполняются соотношения <tex>f[x] \le f[a]</tex> и <tex>f[y] \le f[b]</tex>. В результате перестановки в дереве <tex>T</tex> листьев <tex>a</tex> и <tex>x</tex> получается дерево <tex>T'</tex>, а при последующей перестановке в дереве V листьев <tex>b</tex> и <tex>y</tex> получается дерево <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна <br> <tex>B(T) - B(T') = \sum_{c \in C} f(c)d_T(C) - \sum_{c \in C} f(c)d_{T'}(C) =</tex><br><tex> \\ \\= (f[a] - f[x])(d_T(a) - d_T(x)) \ge 0,</tex>,<br>  поскольку величины <tex>f[a] - f[x]</tex> и <tex>d_T(a) - d_T(x)</tex> неотрицательны. Величина <tex>f[a] - f[x]</tex> неотрицательна, потому что х — лист с минимальной частотой, величина <tex>d_T(a) - d_T(x)</tex> неотрицательна, потому что <tex>a</tex> — лист на максимальной глубине в дереве <tex>T</tex>. Аналогично, перестановка листьев <tex>y</tex> и <tex>b</tex> не приведет к увеличению стоимости, поэтому величина <tex>B(T') - B(T'')</tex> неотрицательна.  Таким образом, выполняется неравенство <tex>B(T') \le B(T'')</tex>, и поскольку <tex>T</tex> — оптимальное дерево, то должно также выполняться неравенство <tex>B(T'') \le B(T')</tex>, откуда следует, что <tex>B(T') = B(T'')</tex>. Таким образом, <tex>T''</tex> — оптимальное дерево, в котором <tex>x</tex> и <tex>y</tex> — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму.

|id=lemma2.

<tex> B(T) = B(T') + f[x] + f[y] </tex> <br> ИЛИ <br> <tex> B(T') = B(T) - f[x] - f[y] </tex>. <br> 

Процедура Huffman Алгоритм Хаффмана дает оптимальный префиксный код.