Математическая логика и теория алгоритмов. Стенюшкина В.А. - 89 стр.

       Время работы алгоритма Huffman для алфавита из n символов есть вели-
чина 0(n log(n)). При этом предполагается, что для нахождения двух объектов,
подлежащих слиянию, используется очередь с приоритетами, а сама очередь
реализована в виде двоичной кучи. Присваивание в строке 2 проводится с по-
мощью процедуры BuildHeap.
       Доказательство того, что жадный алгоритм Huffman дает оптимум, про-
водится в такой последовательности /4/: сначала доказываются леммы 4.1, 4.2,
затем теорема 4.1
       Лемма 4.1 Пусть в алфавите S, каждый символ s∈S имеет частоту f[s] и
пусть x,y∈S-два символа с наименьшими частотами, тогда для S существует оп-
тимальный префиксный код, в котором последовательности битов, кодирую-
щие x и y, имеют одинаковую длину и различаются только в последнем бите.
       Эта лемма показывает, что построение оптимального дерева всегда мож-
но начать со слияния двух символов с наименьшей частотой. Назовем стоимос-
тью слияния сумму частоты сливаемых узлов. Стоимость дерева равна стоимо-
стей всех слияний, необходимых для его построения. Тогда алгоритм Huffman
на каждом шаге выбирает слияние, наименее увеличивающее стоимость.
       Установим теперь свойство оптимальности для подзадач. Пусть фиксиро-
ван алфавит S и два символа х, у этого алфавита, а S’-алфавит, который полу-
чится из S, если удалить х и у и ввести новый символ Z. Рассмотрим кодовые
деревья для S, в которых х и у представлены листьями-братьями. Каждому та-
кому дереву соответствует кодовое дерево для S’, которое получится, если уб-
рать вершины х и у, а их общего родителя считать кодом символа Z. (При этом
каждому кодовому дереву для C’ соответствует два кодовых дерева для C: в
одном из них х − слева, а в другом − справа). Пусть f[s]-частота символа s∈S.
Положим для символов S’ f[z]=f[x]+f[y]; для остальных символов частоты оста-
вим теми же, что и в S. Теперь для обоих алфавитов определены стоимости ко-
довых деревьев.
       Лемма 4.2 Стоимости соответствующих друг другу деревьев Т и Т' отли-
чаются на вершину f[x]+f[y] (в принятом описании).
       Эта лемма показывает, что выполнено свойство оптимальности для по-
дзадач, то есть оптимальное дерево Т соответствует оптимальному дереву Т'
для меньшей задачи.
       Теорема 4.1 Алгоритм Huffman стоит оптимальный префиксный код.
       Доказательство Лемма 4.1. показывает, что оптимальные кодовые деревья
можно искать среди таких, у которых два наиболее редких символа (назовем их
х и у) являются братьями. Им соответствуют деревья для алфавита S', в котором
символы х, у слиты в один символ z. Считая частоту символа z, равной сумме
частот х и у, можно, применив лемму 4.2 и увидев, что остается, найти оптима-
льное кодовое дерево для алфавита S' и затем добавить к вершине z двух пото-
мков, помеченных символами х и у. Именно это и записано в алфавите Huff-
man.
                                4.6.4 Матроиды