15.2. Деревья с минимальной длиной взвешенных путей.

-деревом называется ориентированное дерево, в котором полустепень исхода каждой вершины не превышает т. Напомним, что в ориентированном дереве полустепень захода для корня равна 0, а для остальных вершин — единице. Обычно -дерево изображают так, что корень находится вверху, а все ребра направлены вниз.

Все вершины, находящиеся на одном и том же расстоянии от корня, лежат на одной горизонтальной линии. -дерево изображено на рис. 15.3.

Рис. 15.3. 3-дерево.

Пусть Т — -дерево, а — алфавит, состоящий из m букв. Предположим, что мы приписываем каждому ребру в дереве Т букву из алфавита М так, что не может быть двух ребер, исходящих из одной и той же вершины и помеченных одной и той же буквой. Тогда мы можем приписать каждой вершине дерева Т слово, образуемое конкатенацией букв, которыми помечены ребра, встречающиеся при движении из корня в данную вершину. Такие слова, приписанные листьям дерева Т, называются кодовыми словами, и говорят, что они образуют префиксный код. Например, в случае тернарного дерева, изображенного на рис. 15.3, кодовыми словами являются 00, 010, 120, 121, 22, 20, 21.

Интересным и полезным свойством этих слов в префиксном коде является то, что никакое из слов не совпадает с началом другого. Предположим, что мы закодировали L сообщений словами префиксного кода. Если мы передадим последовательность каких-либо из этих закодированных сообщений по каналам связи, то мы получим на принимающем конце канала последовательность букв, образуемую конкатенацией кодовых слов, соответствующих переданным сообщениям. Чтобы из этой последовательности выделить сообщения, необходимо разложить ее на слова из префиксного кода. Процесс разложения последовательности на кодовые слова называется декодированием, и его можно осуществить с помощью дерева, соответствующего префиксному коду. Например, рассмотрим последовательность 120202200, которая образована конкатенацией некоторых слов префиксного кода, соответствующего дереву, изображенному на рис. 15.3. Чтобы декодировать эту последовательность, рассмотрим составляющие ее буквы слева направо. В соответствии с этим просмотром мы двигаемся по дереву, начиная с корня вдоль ребер, которые соответствуют рассматриваемым буквам, до тех пор пока мы не дойдем до листа дерева. Кодовое слово, соответствующее этому листу, является первым словом в данной последовательности. Таким образом, мы получаем 120 в качестве первого слова в последовательности 120202200. Затем мы повторяем процесс декодирования для оставшейся последовательности 202200 и выделяем 20, 22, 00 в качестве второго, третьего и четвертого кодовых слов в последовательности 120202200.

Из процесса декодирования, описанного выше, ясно, что стоимость декодирования кодового слова пропорциональна числу букв в этом слове. Если — частота появления сообщения то ожидаемая стоимость декодирования зависит от суммы где -длина пути от корня до листа, соответствующего сообщению Сумма называется длиной взвешенных путей дерева. Таким образом, ожидаемую стоимость декодирования можно свести к минимуму таким выбором длин кодовых слов, что полученное дерево будет иметь минимальную длину взвешенных путей. Это рассуждение приводит нас к задаче построения -дерева с минимальной длиной взвешенных путей по заданному множеству весов

Прежде чем рассмотреть решение этой задачи, обсудим другой случай, в котором эта задача встречается.

Пусть нам дано L списков . Предположим, что каждый список состоит из целых чисел, расположенных в неубывающем порядке. Мы хотели бы слить эти списки в единый список, элементы которого также располагались в неубывающем порядке. Чтобы выполнить это, мы можем слить, во-первых, любые два из этих списков, например и получить новый список S. Затем мы можем слить любые два списка из множества и продолжить слияние до тех пор, пока не будет получен одии

список. Для описания такого способа слияния можно использовать бинарное дерево.

Например, рассмотрим дерево, изображенное на рис. 15.4, которое описывает порядок слияния пяти списков Вначале мы сливаем списки чтобы получить . Затем сливаются списки чтобы получить На следующем шаге сливаются списки и мы получаем Наконец сливаются списки в результате чего получается один требуемый список.

Одним из путей слияния двух произвольных списков является следующий способ. Возьмем первые элементы, т. е. минимальные элементы из двух данных списков. Считаем наименьший из этих элементов первым элементом нового списка. Элемент, выбранный таким образом, удаляем из исходного списка. Повторяем эту операцию над теми же самыми двумя списками, один из которых стал короче, до тех пор, пока они не сольются в единый список.

Ясно, что стоимость слияния любых двух списков пропорциональна общему числу элементов в списках. Поэтому стоимость слияния списков равна где — число процессов слияния, в которых участвуют элементы списка

Например, стоимость слияния списков в соответствии с деревом, изображенным на рис. 15.4, равна

Рис. 15.4.

Из рис. 15.4 видно, что в этом случае фактически равно длине пути из корня дерева в лист, соответствующий Таким образом, задача минимизации стоимости слияния списков эквивалентна задаче построения бинарного дерева с минимальной длиной взвешенных путей для весов

В работе [15.18] приводится элегантное решение рассмотренной выше задачи. Остальная часть этого раздела посвящена алгоритму Хаффмана. Рассмотрим -дерево Т с L листьями. Пусть — длины путей из корня в листы дерева Т. Назовем длиной пути соответствующего листа, а вектор — вектором длин путей дерева Т. Определим характеристическую сумму вектора К следующим образом:

    (15.11)

Определим необходимые и достаточные условия для того, чтобы вектор X был вектором длин путей -дерева. При этом мы предполагаем, что каждое положительное число.

Лемма 15.1. Характеристическая сумма вектора длин путей -дерева меньше или равна единице.

Доказательство проведем индукцией по максимальной длине в векторе X. Если максимальная длина в X равна единице, то все равны единице. Очевидно, в этом случае лемма справедлива. Пусть лемма верна для каждого вектора длин путей, в котором максимальная длина меньше k. Предположим, что максимальная длина в равна k. Пусть в соответствующем -дереве Т вершины являются сыновьями корня . Отметим, что полустепень исхода меньше или равна . Пусть — поддерево дерева Т, имеющего в качестве корня. Ясно, что длины путей в поддереве короче не единицу соответствующих путей в Т. Таким образом, если S — характеристическая сумма вектора длин путей дерева , то . Так как и по предположению индукции для всех , то

Лемма 15.2. Вектор где каждое — положительное число, является вектором длин путей -дерева, если он удовлетворяет условию

    (15.12)

Доказательство. Расположим длины таким образом, что

Пусть — число длин, равных . Тогда

Умножим выражение (15.12) на и получим

    (15.13)

Пусть где — неотрицательны, причем и определим и следующим образом:

Тогда мы можем добавить к левой части выражения (15.13), не нарушая неравенства. Таким образом,

    (15.11)

Отметим, что где

    (15.15)

Тогда, разделив выражение (15.14) на , получим

    (15.16)

Значение левой части неравенства является характеристической суммой вектора длиной в которой максимальная длина короче на единицу максимальной длины в данном векторе X. Докажем лемму индукцией по величине максимальной длины. Если то для всех i и из выражения (15.12) следует, что

Ясно, что лемма верна в этом случае, поскольку — вектор длин путей -дерева, содержащего L ребер, каждое из которых выходит из корня.

Затем предположим, что лемма верна для всех векторов, в которых максимальная длина меньше

Пусть максимальная длина в X равна k. Как мы уже упоминали ранее, мы можем построить вектор V длиной причем максимальная длина равна . В существует по меньшей мере длин, равных а остальные длин вектора X совпадают с первыми длинами вектора X. Отметим, что либо

Так как X удовлетворяет условию (15.16), то по предположению индукции следует, что существует -дерево Т с X в качестве вектора длин путей. Рассмотрим любые листьев дерева Т с длинами путей, равными Если мы присоединим m ребер к каждой из каких-либо а выделенных вершин и ребер к оставшейся вершине, если она существует, то мы получим новое -дерево Т, которое имеет листьев с длинами путей, равными к. Остальные длины путей совпадают с первыми длинами путей X. Таким образом, — вектор длин путей дерева Т.

Вектор длин путей называется оптимальным для вектора весов если он минимизирует сумму

Если — оптимальный вектор для W, то из следует, что Предположим, что Случай тривиален, поэтому мы предполагаем в дальнейшем, что Следующий результат является основой алгоритма Хаффмана построения оптимального вектора длин путей для заданного вектора весов.

Теорема 15.2. Пусть — оптимальный вектор длин путей для вектора весов Предположим, что

Тогда где если . В случае величина d определяется следующим образом:

Доказательство. По существу, в теореме утверждается, что вектор длин путей содержит по меньшей мере d длин, равных максимальной длине в том случае, если он оптимален. Доказательство теоремы для случая, когда проводится просто. Полому мы рассмотрим случай

Из условия (15.12), накладываемого на характеристическую сумму, следует, что

    (15.18)

Покажем, что

Если условие (15.19) неверно, то Таким образом,

Поделив это выражение на получим

Однако это противоречит тому, что — оптимальный вектор. Поэтому соотношение (15 19) верно.

Из того, что следует, что для любого целого неотрицательного числа к. Поэтому

где . Тогда

    (15.21)

Из выражений (15.18) и (15.19) следует, что сумма неотрицательна и меньше

Таким образом, из выражений (15.20) и (15.21) следует

Предположим, что j — последний индекс, для которого верно, что Тогда верно, что

Чтобы показать, что используем (15.22). Тем самым теорема будет доказана. Мы можем переписать (15.22) следующим образом:

Левая часть вышеприведенного равенства делится на , и мы получаем следующее:

Если тогда для некоторого положительного целого числа к. Если тогда для некоторого положительного целого числа k. Если тогда для некоторого положительного целого числа .

Таким образом, из выражения (15.17) следует, что если то если то если то

Опишем алгоритм Хаффмана для построения оптимального вектора длин путей по заданному вектору весов Обозначим число весов в векторе весов через L. Если то соответствующим оптимальным вектором длин путей является вектор, состоящий из единиц. Поэтому мы предполагаем, что

Начиная с алгоритм Хаффмана порождает такую последовательность векторов весов, что Для каждого - мы определим в соответствии с выражением (15.17), т. е. если

Иначе

Мы используем при построении из Алгоритм затем начинает с вектора и строит такую последовательность векторов длин путей , что оптимальный вектор длин путей для Мы предполагаем, что длины в каждом векторе X расположены в том же порядке, что и веса в соответствующем векторе

Алгоритм 15.3. Оптимальный вектор длин путей (Хаффман).

S1. -данный вектор весов. Пусть

S2. Пусть , где Построить следующим образом:

1) Вычислить d; в соответствии с выражением (15.23).

2) Вычислить , т. е. Р — сумма последних d; весов состоит из весов расположенных в невозрастающем порядке.

S3. Пусть Если то идти к шагу Иначе идти к шагу

S4. Пусть (Отметим, что теперь ). Положить

S5. Построить следующим образом:

1) Каждому весу из первых весов в векторе приписывается длина, равная его длине в векторе

2) Каждому весу из последних весов в векторе приписывается длина, которая больше, чем длина для веса Р, - в векторе единицу.

S6. Если то HALT; оптимальный вектор длин путей для вектора весов Иначе положить и идти к шагу

Ясно, что — вектор длин путей. Из выражения (15.23) следует, что для всех i. Построение в алгоритме гарантирует, что — вектор длин путей для всех

Работа алгоритма Хаффмана проиллюстрирована на рис. 15.5 для Деревья соответствующие векторам длин путей показаны на рис. 15.6. (Отметим, что строится из добавлением ребер к

Рис. 15.5. Иллюстрация алгоритма Хаффмана.

листу в представляющему вес Покажем корректность алгоритма Хаффмана.

Теорема 15.3. Пусть

— векторы весов и длин путей, построенные алгоритмом Хаффмана. Для любого оптимальный вектор длин путей для вектора весов

Доказательство. Ясно, что вектор длин путей оптимален для Покажем, что если оптимален для то вектор X; оптимален для Допустим противное, а именно что оптимален для а не оптимален для Тогда пусть — оптимальный вектор длин для вектора весов Пусть причем причем Так как X; не является оптимальным для получим

Из шага в построении Хаффмана следует, что для некоторого следует (Отметим, что совпадает с а остальные есть Верно также, что

Таким образом,

    (15.25)

Так как X — оптимальный вектор, то мы получаем из теоремы 15.2, что тот же самый тип преобразования, как и в случае перехода от то можем получить из вектор длин путей который

(см. скан)

Рис. 15.6. а — дерево дерево Т в — дерево - дерево .

удовлетворяет условию

    (15.26)

Теперь мы можем показать, используя выражение (15.24) — (15.26), что что не является оптимальным вектором длин путей. Пришли к противоречию.