355
правок
Изменения
→Корректность алгоритма Хаффмана
== Корректность алгоритма Хаффмана ==
Чтобы доказать корректность жадного алгоритма Хаффмана, покажем, что в задаче о построении оптимального префиксного кода проявляются свойства жадного выбора и оптимальной подструктуры. В сформулированной ниже лемме показано соблюдение свойства жадного выбора.
{{Лемма
Тогда для алфавита <tex>C</tex> существует оптимальный префиксный код, кодовые слова символов <tex>x</tex> и <tex>y</tex> в котором имеют одинаковую максимальную длину и отличаются лишь последним битом.
|proof=
Пусть <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>T'</tex> листьев <tex>b</tex> и <tex>y</tex> получается дерево <tex>T''</tex>. Разность стоимостей деревьев Т и Т" равна
<tex>B(T) - B(T') = \sum\limits_{c \in C} f(c)d_T(C) - \sum\limits_{c \in C} f(c)d_{T'}(C)= \\ \\
поскольку величины <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> — находящиеся на максимальной глубине дочерние листья одного и того же узла, что и доказывает лемму.
}}
|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 C - \backslash \{x,y\}</tex> выполняется соотношение <tex>d_T(C) = d_{T'}(c)</tex>, следовательно, <tex>f[c]d_T(C) = f[c]d_{T'}(c)</tex>. Поскольку <tex>d_T(x) = d_{T}(y) = d_{t'}(z) + 1</tex>, получаем соотношение<br>
<tex>f[x]d_T(x) + f[y]d_{T}(y) = (f[x] + f[y])(d_{T'}(z) + 1) = f[z]d_{T'}(z) + (f[x] + f[y])</tex>
<br>
