Материал: 1_2_3_ДХафф

13

Эта страница «сцепляется» с 1.1

1.2. Код ФаноШеннона

В методе, предложенном Р. Фано (R. M. Fano) и К. Шенноном (C. E. Shannon), префиксный код (и соответственно – кодовое дерево) строится следующим образом («сверху вниз»). Пусть набор (w_i)₁ⁿ – упорядочен, а именно: w₁  w₂  … w_n  1  w_n. В качестве корня дерева выбирается такой узел (и соответственно набор (w_i)₁ⁿ разбивается на 2 поднабора и так), что веса поддеревьев различаются минимально, т. е. если k = , то коды сообщений оказываются в левом поддереве, а коды сообщений  в правом поддереве. Эта процедура повторяется для поддеревьев до тех пор, пока не будет получен лист в качестве текущего поддерева.

Пример построения кода ФаноШеннона. Пусть n = 5, m = 20 и

Т

20(АБВГД)

Здесь каждому узлу дерева приписаны символ или группа символов и их веса. Кодовые слова даны в таблице

Полная длина кода есть L = 2(8 + 3 + 3) + 3(3 + 3) = 46 бит. Равномерный код (по 3 бита) дал бы суммарную длину L = 320 = 60 бит.

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

Оказывается, что для рассмотренного примера можно найти более экономный (в смысле значения L) код. Действительно, следующее кодовое дерево

порождает код

Для этого кода имеем L = 81+ 3(3 + 3 + 3 + 3) = 44 бита, что меньше, чем дает код ФаноШеннона. Этот пример показывает, что код ФаноШеннона не является оптимальным кодом.

1.3. Задача оптимального кодирования

Итак, задача построения оптимального префиксного кода есть задача минимизации функции L = _i=1..n w_i l_i  целочисленных положительных переменных (l_i)₁ⁿ при заданном наборе (w_i)₁ⁿ и при условии (пока не формализованном) выполнения свойства префиксности кода. Набор переменных (l_i)₁ⁿ, минимизирующий L, определяет структуру дерева (кода).

Интересно, что аналогичным образом формулируются и некоторые, казалось бы, совершенно другие задачи.

Задача поиска (тестирования). Производится поиск на основе последовательных сравнений (решений) или последовательных тестов: каждый новый вопрос (тест) задается (проводится) в зависимости от предыдущих ответов (от результатов предыдущих тестов). Рассматриваются бинарные тесты (задаются вопросы с ответами «да» или «нет»). Этот процесс можно описать с помощью бинарных деревьев решений. Узлы в таких деревьях соответствуют вопросам (тестам), ветви – исходам теста («да»/«нет» или 1/0). Деревья – строго бинарные. Лист дерева решений соответствует завершению (исходу) поиска (тестирования). В качестве примера можно привести анализ алгоритма бинарного поиска, приведенный в [8, 5.3]. Пусть {₁, ₂, …, _n} – множество исходов поиска. Число шагов поиска (длина теста) есть длина пути l_i в дереве решений от корня до листа _i. Пусть  w_i – вероятность P(x  _i) или частота предъявления элемента для поиска, приводящего к исходу поиска _i. Тогда M(l) = _i=1..n w_i l_i  есть математическое ожидание времени поиска (среднее число шагов поиска или последовательного теста). Итак, задача поиска формулируется следующим образом: по заданным n, (_i)₁ⁿ и (w_i)₁ⁿ, где w_i = P(x  _i), построить стратегию поиска (дерево решений), минимизирующую математическое ожидание числа шагов поиска M(l) = _i=1..n w_i l_i.

Задача слияния множества упорядоченных списков. Заданы n упорядоченных списков S₁, S₂, …, S_n. Пусть  i  1..n: w_i = S_i  длина списка  S_i. Требуется построить один упорядоченный список S путем попарного слияния исходных S₁, S₂, …, S_n и получаемых в процессе этих действий промежуточных упорядоченных списков. Базовая операция слияния двух упорядоченных списков Merge (S_i, S_j) требует w_i + w_j  элементарных операций (сравнений и перемещений). Алгоритм Merge (S_i, S_j) можно найти, например, в [8, 4.5]. Общее количество операций зависит от порядка попарных слияний. Этот порядок можно задать строго бинарным деревом слияний. Например, дерево

описывает следующую последовательность слияний:

S_{1, 2} = Merge (S₁, S₂),

S_{5, 6} = Merge (S₅, S₆),

S_{1, 2, 3} = Merge (S_{1, 2}, S₃),

S_{4, 5, 6} = Merge (S_{5, 6}, S₄),

S = Merge (S_{1, 2, 3}, S_{4, 5, 6}).

Легко видеть, что здесь общее количество элементарных операций есть 3w₁ + 3w₂  + 2w₃ + 2w₄ + 3w₅ + 3w₆.

В общем случае совокупное количество элементарных операций есть _i=1..n w_i l_i , где l_i – количество слияний с участием элементов списка S_i  или, что то же, уровень листа S_i  в дереве слияний. Требуется построить дерево слияний, структура которого определит оптимальный порядок слияний, а минимальное общее число операций _i=1..n w_i l_i  будет определяться величинами (l_i)₁ⁿ.

1.4. Метод Хаффмана

Элегантное решение (алгоритм) для задачи построения оптимального префиксного кода нашел Д. Хаффман (D. A. Haffman) [18]. Дадим описание этого алгоритма в рекурсивной форме.

Обозначим W_n = (w_i)₁ⁿ. Пусть набор W_n  упорядочен:

w₁  w₂  … w_n  1  w_n.

Если n = 2, то завершаем процесс кодирования, приписав сообщению с весом w₁  код 1, а сообщению с весом w₂  – код 0. Иначе (т. е. при n  2) выполняем следующие действия:

1. Из минимальных весов w_n  1  и  w_n образуем .

2. Из набора W_n исключаем элементы w_n  1  и  w_n и добавляем в него новый элемент . Полученный набор обозначим .

3. Решаем таким же способом задачу с набором весов , а затем в полученном решении заменяем узел (лист) на поддерево из двух листьев w_n  1  и  w_n, приписав им коды 1 и 0 соответственно.