скачать doc
1. ДЕРЕВЬЯ ХАФФМАНА
Рассмотрим пример применения деревьев в задаче кодирования (упаковки, сжатия) сообщений.
1.1. Задача кодирования сообщений. Префиксные коды и деревья
Пусть задан алфавит A = {1, 2, …, n}, где i – символы алфавита или элементарные сообщения (i 1..n). Пусть имеется сообщение («текст» или последовательность m символов, т.е. элементарных сообщений):
(a1, a2, …, am), j 1..m: aj A.
В этом тексте (входной последовательности символов) каждый символ алфавита i встречается wi раз. Более формально ( j 1..m: (i 1..n: aj = i)) и ( i 1..n: wi = (N j 1..m: aj = i)), где N – квантор счета. При этом i=1..n wi = m.
Требуется закодировать входное сообщение (a1, a2, …, am), т.е. для каждого символа алфавита i получить его кодовое слово сi , и породить выходную последовательность кодовых слов, заменив каждое вхождение символа во входной последовательности его кодом. При этом желательно получать закодированные сообщения возможно меньшей длины. Будем рассматривать только двоичные коды, т.е. такие, что для i 1..n будем иметь сi = (сi(1), сi(2),…, сi(li)), где сi(j) {0, 1} и где li – длина кодового слова сi.
Пример. Пусть A = {А, Б, В, Г}. Здесь n = 4, 1= «А», 2= «Б», 3= «В», 4= «Г». Пусть задан также входной текст «АББАГАВ», т.е. здесь m = 7 и W = (wi)1n= (3, 2, 1, 1).
Способ кодирования 1: равномерный 3-битный код.
| wi | 3 | 2 | 1 | 1 |
| i | А | Б | В | Г |
| сi | 001 | 010 | 011 | 100 |
Код(«АББАГАВ») = 001 010 010 001 100 001 011
Здесь и далее в примерах пробелы в коде сообщения введены для удобства чтения. На самом деле никаких «разделителей» в коде нет. Длина закодированного текста есть 73 = 21 бит.
Способ кодирования 2: равномерный 2-битный код.
| wi | 3 | 2 | 1 | 1 |
| i | А | Б | В | Г |
| сi | 00 | 01 | 10 | 11 |
Код(«АББАГАВ») = 00 01 01 00 11 00 10
Длина закодированного текста есть 72 = 14 бит.
Способ кодирования 3: неравномерный код. Здесь длины кодовых слов различных символов могут быть различны.
| wi | 3 | 2 | 1 | 1 |
| i | А | Б | В | Г |
| сi | 0 | 10 | 110 | 111 |
Код(«АББАГАВ») = 0 10 10 0 111 0 110
Длина закодированного текста есть
i=1..n wi li = w1 l1 + w2 l2 + w3 l3 + w4 l4 = 31 + 22 + 13 + 13 = 13 бит.
Третий способ приводит к коду меньшей длины, чем первый и второй способы, поскольку при этом чаще встречающиеся символы кодируются более короткими кодовыми словами. Однако в этом случае неясно, как при декодировании выделять коды отдельных символов, если длина кодов разная. Использование специальных разделяющих кодов (как, например, в азбуке Морзе) удлинило бы закодированное сообщение.
Оказывается, что достаточным условием однозначного декодирования неравномерного кода является свойство префиксности кода. При этом декодирование возможно за один проход («на лету»).
Код называется префиксным, если никакое кодовое слово не является началом (префиксом) другого кодового слова. Более формально это можно выразить так. Пусть C = {c1, c2, …,cn} – код, а сi – кодовое слово для i и сi = (сi(1), сi (2),…, сi(li)). Код C – называется префиксным, если для любых кодовых слов сi и сj (ij) имеем
(li lj) (сi(1), сi(2),…, сi(li)) (сj(1), сj(2),…, сj(li)).
Легко убедится, что использованный выше при третьем способе кодирования неравномерный код является префиксным.
Между двоичными кодами и бинарными деревьями имеется соответствие. Рассмотрим сначала соответствие «код» «дерево». Пусть задан код, например, c(А) =0 , c(Б) = 10, c(В) = 110, c(Г) = 111. Последовательность нулей и единиц в кодовом слове задает путь от корня до узла дерева, если считать, что, например, 0 означает переход к левому сыну, а 1 – к правому сыну текущего узла дерева. Для префиксного кода коды
символов сопоставляются листьям в кодовом дереве. Действительно, для указанных в примере кодов последовательно получаем
Последнее (правое) дерево соответствует заданному коду.
Пусть теперь задано бинарное дерево, листьям которого приписаны символы алфавита. Припишем ветвям дерева двоичные символы 0 и 1: ветвь, ведущую к левому сыну, пометим нулем, а ведущую к правому сыну – единицей. Тогда последовательность нулей и единиц, полученная обходам вершин дерева от корня к листу, может рассматриваться как префиксный код символа, приписанного к этому листу. Например, бинарному дереву
соответствует равномерный (все листья на одном уровне) код, совпадающий с кодом, полученным способом кодирования 2 в ранее рассмотренном примере. Следующее бинарное дерево
представляет неравномерный префиксный код
| i | А | Б | В | Г |
| сi | 0 | 11 | 100 | 101 |
Заметим, что если рассмотреть тот же пример текста «АББАГАВ», то данный код отличается от кода, полученного ранее способом кодирования 3. Однако суммарная длина закодированного текста и здесь будет равна 13 битам. Действительно, т. к. (wi)1n= (3, 2, 1, 1), то i=1..n wi li = 31 + 22 + 13 + 13 = = 13 бит. Листья в кодовом дереве располагаются на тех же уровнях, что и в ранее рассмотренном примере, а сами деревья, соответствующие этим различным кодам, отличаются лишь перестановкой некоторых поддеревьев.
Префиксный код называется полным, если добавление к нему любого нового кодового слова нарушает свойство префиксности. В терминологии кодовых деревьев это означает, что полному коду соответствует строго бинарное дерево, т. е. такое бинарное дерево, все узлы которого, кроме листьев, имеют ровно двух сыновей. Например, строго бинарное дерево
соответствует полному коду cА = 0, cБ = 10, cВ = 11. Дерево (не строго бинарное)
задает неполный код cА = 0, cБ = 100, cВ = 101. В такой код можно добавить, например, кодовое слово cГ = 11, не изменяя остальные коды. Полученное после добавления кодовое дерево
является уже строго бинарным, а новый код – полным.
Итак, в кодовом дереве, соответствующем префиксному коду, символами помечаются только листья, и их ровно столько сколько символов в алфавите. Длина li кодового слова сi есть длина пути от корня до листа i.
Рассмотрим процессы кодирования и декодирования. Пусть построено кодовое дерево. Кодирование, т. е. порождение кодовых слов для всех символов алфавита, происходит следующим образом. Кодовое слово для символа i получают, проходя по дереву от листа, соответствующего i , к корню. При этом код выписывается справа налево. При подъёме по дереву от левого сына к отцу в начало кодового слова добавляется 0, а при подъёме от правого сына к отцу в начало кодового слова добавляется 1. При декодировании расшифровка очередного кодового слова получается последовательным чтением битов закодированного сообщения и синхронным движением по кодовому дереву от корня до листа так, что бит 0 вызывает переход к левому сыну, а бит 1 – к правому.
Далее для полной длины закодированного текста (последовательности сообщений) будем использовать обозначение
L = i=1..n wi li = w1 l1 + w2 l2 + … + wn ln.
При хорошем кодировании полная длина кода L должна быть малой. Естественно искать код, минимизирующий L, как функцию от (li)1n. При этом заданными считаются n и (wi)1n, а найти требуется (li)1n с условием, что все li являются длинами кодовых слов префиксного кода.
Этой задаче можно дать вероятностную (стохастическую) интерпретацию. Рассмотрим входной поток независимых сообщений. Пусть wi – вероятность появления сообщения (символа) i во входном потоке. Тогда L = i=1..n wi li есть математическое ожидание длины кода случайно выбранного символа (или с эмпирической точки зрения – средняя длина кода сообщения).
Переход к вероятностной («частотной») интерпретации может быть пояснен следующим образом. Разделим на m левые и правые части равенств i=1..n wi = m и L = i=1..n wi li и обозначим pi = wi / m и Lp = L / m. Тогда получим i=1..n pi = 1 и Lp = i=1..n pi li. Здесь естественно называть pi частотами вхождения символов в текст, а Lp – средней длиной кодовых слов.