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

случае неравномерного кода разделяется на части 0-0-101-1101 и декодируется
как aabc.
      Оптимальному для данного файла коду всегда соответствует двоичное
дерево, в котором любая вершина (кроме листьев) имеет двух непосредствен-
ных потомков. Отсюда следует, что дерево оптимального префиксного кода с n
символами содержит n листьев и n-1 узлов, не являющихся листьями. Рассмот-
ренный равномерный код, как легко видеть, этим свойством не обладает.
      Зная дерево Т, соответствующее префиксному коду, найдем количество
битов, необходимое для кодирования файла. Пусть ƒ(S) обозначает число вхо-
ждений символа S в файл, gT(S) – глубину соответствующего листа в дереве
(длину последовательности битов, кодирующей S). Тогда для кодирования
файла потребуется
                               B(T)=Σ s∈Sƒ(s)gT(s)

битов. Число B(T) называется стоимостью дерева Т. Здесь S={S} - алфавит
файла.

                          4.6.3 Коды Хаффмена

      Хаффмен построил жадный алгоритм, который строит оптимальный пре-
фиксный код (код Хаффмена). Фактически алгоритм строит дерево Т, соответс-
твующие оптимальному коду снизу вверх, начиная с множества |S| листьев и
выполняя |S|-1 «слияние». Первому слиянию подлежат листья с наименьшей
частотой, а очередным «слиянием» - поддеревья с наименьшей частотой. Для
рассмотренного ранее примера последовательность построения дерева дана на
рисунке 4.7 (|S|=6=n).
      Синтезируя полученный элементы, получим дерево Т, как на рисунке 4.6.
Псевдокод алгоритма можно записать с применением процедур Allocate_Nod,
Extract_Min, Insert, знакомых по работе с кучами /4/.
       Huffman (S)
      1    n←|S|
      2    0 ←S
      3    for i←1 to n-1
      4          do z← Allocate_Nod ()
      5             x←left [z]← Extract_Min (0)
      6            y←right [z]← Extract_Min (0)
      7            f[z]←f[x]+f[y]
      8            Insert (0,7)
      9    return Extract_Min (0)
      End {Huffman}