Изменения
Переделано доказательство второй леммы
|about=2
|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>C</tex> путем удаления символов <tex>x</tex> и <tex>y</tex> и добавления нового символа <tex>z</tex>, так что <tex>C' = C \backslash \{ x, y \} \cup {z}</tex>. По определению частоты <tex>f</tex> в алфавите <tex>C'</tex> совпадают с частотами в алфавите <tex>C</tex>, за исключением частоты <tex>f[z] = f[x] + f[y]</tex>. Пусть <tex>T'</tex> — произвольное дерево, представляющее оптимальный префиксный код для алфавита <tex>C'</tex> Тогда дерево <tex>T</tex>, полученное из дерева <tex>T'</tex> путем замены листа <tex>z</tex> внутренним узлом с дочерними элементами <tex>x</tex> и <tex>y</tex>, представляет оптимальный префиксный код для алфавита <tex>C</tex>.
|proof=Сначала покажем, что стоимость <tex>B(T)</tex> дерева <tex>T</tex> можно выразить может быть выражена через стоимость <tex>B(T')</tex> дерева <tex>T'</tex>. Для каждого символа <tex>c \le in C \backslash \{x,y\}</tex> выполняется соотношение верно <tex>d_T(C) = d_{T'}(c)</tex>, следовательнозначит, <tex>f[c]d_T(Cc) = f[c]d_{T'}(c)</tex>. Поскольку Так как <tex>d_T(x) = d_{T}d_T(y) = d_{tT'}(z) + 1</tex>, получаем соотношение<br>то <tex>f[x]d_T(x) + f[y]d_{T}d_T(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex><br>из которого чего следует равенство <br>, что
<tex> B(T) = B(T') + f[x] + f[y] </tex>
или
<tex> B(T') = B(T) - f[x] - f[y] </tex> Докажем лемму от противного.Предположим, что дерево <tex>T</tex> не представляет оптимальный префиксный код для алфавита <tex>C</tex>. Тогда существует дерево <tex>T''</tex> такое, что <tex>B(T'') < B(T)</tex>. Согласно лемме (1), элементы <tex>x</tex> и <tex>y</tex> можно считать дочерними элементами одного узла. Пусть дерево <tex>T'''</tex> получено из дерева <tex>T''</tex> заменой элементов <tex>x</tex> и <tex>y</tex> листом <tex>z</tex> с частотой <tex>f[z] = f[x] + f[y]</tex>. Тогда <tex>B(T''') = B(T'') - f[x] - f[y] < B(T) - f[x] - f[y] = B(T')</tex>,
}}
