скачать doc
1.2. Код Фано-Шеннона
В методе, предложенном Р. Фано (R.M. Fano) и К. Шенноном (C.E. Shannon) префиксный код (и соответственно – кодовое дерево) строится следующим образом («сверху вниз»). Пусть набор (wi)1n – упорядочен, а именно: w1 w2 … wn 1 wn. В качестве корня дерева выбирается такой узел (и соответственно набор (wi)1n разбивается на два поднабора
и 
так), что веса поддеревьев различаются минимально, т. е. коды сообщений 
оказываются в левом поддереве, а коды сообщений 
оказываются в правом поддереве, если k = 
. Эта процедура повторяется для поддеревьев до тех пор, пока не будет получен лист в качестве текущего поддерева.Пример построения кода Фано-Шеннона. Пусть n = 5, m = 20 и
| wi | 8 | 3 | 3 | 3 | 3 |
| i | А | Б | В | Г | Д |
Тогда кодовое дерево Фано-Шеннона есть
Кодовые слова даны в таблице
| wi | 8 | 3 | 3 | 3 | 3 |
| i | А | Б | В | Г | Д |
| ci | 00 | 01 | 10 | 110 | 111 |
Полная длина кода есть L = 2(8+3+3)+3(3+3) = 46 бит. Равномерный код (по 3 бита) дал бы суммарную длину L = 320 = 60 бит.
Отметим, что левые и правые поддеревья в кодовом дереве можно менять местами. При этом код будет изменяться, но величина L не изменится. Для определенности удобно, например, с целью облегчения проверки выполнения заданий, левым поддеревом выбирать поддерево с меньшим весом. Тогда в последнем примере будем иметь результирующее дерево следующего вида
Оказывается, что для рассмотренного примера можно найти более экономный (в смысле величины L) код. Действительно, следующее кодовое дерево
порождает код
| wi | 8 | 3 | 3 | 3 | 3 |
| i | А | Б | В | Г | Д |
| ci | 0 | 100 | 101 | 110 | 111 |
Для этого кода имеем L = 81+3(3+3+3+3) = 44 бита, что меньше, чем дает код Фано-Шеннона. Этот пример показывает, что код Фано-Шеннона не является оптимальным кодом.
1.3. Задача оптимального кодирования
Итак, задача построения оптимального префиксного кода есть задача минимизации функции L = i=1..n wi li целочисленных положительных переменных (li)1n при заданном наборе (wi)1n и при условии (пока не формализованном) выполнения свойства префиксности кода. Набор переменных (li)1n, минимизирующий L, определяет структуру дерева (кода).
Интересно, что аналогичным образом формулируются и некоторые, казалось бы, совершенно другие задачи.
Задача поиска (тестирования). Производится поиск на основе последовательных сравнений (решений) или последовательных тестов: каждый новый вопрос (тест) задаётся (проводится) в зависимости от предыдущих ответов (от результатов предыдущих тестов). Рассматриваются бинарные тесты (задаются вопросы с ответами «да» или «нет»). Этот процесс можно описать с помощью бинарных деревьев решений. Узлы в таких деревьях соответствуют вопросам (тестам), ветви – исходам теста («да»/«нет» или 1/0). Деревья – строго бинарные. Лист дерева решений соответствует завершению (исходу) поиска (тестирования). В качестве примера можно привести анализ алгоритма бинарного поиска, приведенный в [*] (раздел 5.3). Пусть {1, 2, …, n} – множество исходов поиска. Число шагов поиска (длина теста) есть длина пути li в дереве решений от корня до листа i. Пусть wi – вероятность P(x i) или частота предъявления элемента для поиска, приводящего к исходу поиска i. Тогда M(l) = i=1..n wi li есть математическое ожидание времени поиска (среднее число шагов поиска или последовательного теста). Итак, задача поиска формулируется следующим образом: по заданным n, (i)1n и (wi)1n, где wi = P(x i), построить стратегию поиска (дерево решений), минимизирующую математическое ожидание числа шагов поиска M(l) = i=1..n wi li.
Задача слияния множества упорядоченных списков. Заданы n упорядоченных списков S1, S2, …, Sn. Пусть i 1..n: wi = Si длина списка Si. Требуется построить один упорядоченный список S путем попарного слияния исходных S1, S2, …, Sn и получаемых в процессе этих действий промежуточных упорядоченных списков. Базовая операция слияния двух упорядоченных списков Merge (Si, Sj) требует wi + wj элементарных операций (сравнений и перемещений). Алгоритм Merge (Si, Sj) можно найти, например, в [*], раздел 4.5. Общее количество операций зависит от порядка попарных слияний. Этот порядок можно задать строго бинарным деревом слияний. Например, дерево
описывает следующую последовательность слияний:
S1, 2 = Merge (S1, S2),
S5, 6 = Merge (S5, S6),
S1, 2, 3 = Merge (S1, 2, S3),
S4, 5, 6 = Merge (S5, 6, S4),
S = Merge (S1, 2, 3, S4, 5, 6).
Легко видеть, что здесь общее количество элементарных операций есть 3w1 + 3w2 + 2w3 + 2w4 + 3w5 + 3w6.
В общем случае совокупное количество элементарных операций есть i=1..n wi li , где li – количество слияний с участием элементов списка Si или, что то же, уровень листа Si в дереве слияний. Требуется построить дерево слияний, структура которого определит оптимальный порядок слияний, а минимальное общее число операций i=1..n wi li будет определяться величинами (li)1n.