Деревья кодирования по Хаффману

Эта статья дает возможность попрактиковаться в использовании списковых структур и абстракции данных для работы с множествами и деревьями.
Советую ознакомиться с предыдущей записью: Представление множеств и КодХаффмана
Они применяются к методам представления данных как последовательностей из единиц и нулей (битов). Например, стандартный код ASCII, который используется для представления текста в компьютерах, кодирует каждый символ как последовательность из семи бит. Семь бит позволяют нам обозначить 2⁷, то есть 128 различных символов. В общем случае, если нам требуется различать n символов, нам потребуется log₂N бит для каждого символа.
*-Нравится статья? Кликни по рекламе! :)

Если все наши сообщения составлены из восьми символов A, B, C, D, E, F, G, и H, мы
можем использовать код с тремя битами для каждого символа, например

С таким кодом, сообщение
BACADAEAFABBAAAGAH
кодируется как строка из 54 бит
001000010000011000100000101000001001000000000110000111

Такие коды, как ASCII и наш код от A до H, известны под названием кодов с фиксированной длиной, поскольку каждый символ сообщения они представляют с помощью одного и того же числа битов. Иногда полезно использовать и коды с переменной длиной (variable-length), в которых различные символы могут представляться различным числом битов. Например, азбука Морзе не для всех букв алфавита использует одинаковое число точек и тире. В частности, E, наиболее частая (в английском) буква, представляется с помощью одной точки. В общем случае, если наши сообщения таковы, что некоторые символы встречаются очень часто, а некоторые очень редко, то мы можем кодировать свои данные более эффективно (т. е. с помощью меньшего числа битов на сообщение), если более частым символам мы назначим более короткие коды. Рассмотрим следующий код для букв с A по H:

С таким кодом то же самое сообщение преобразуется в строку
100010100101101100011010100100000111001111
В этой строке 42 бита, так что она экономит более 20% места по сравнению с приведенным выше кодом с фиксированной длиной.
Одна из сложностей при работе с кодом с переменной длиной состоит в том, чтобы узнать, когда при чтении последовательности единиц и нулей достигнут конец символа. В азбуке Морзе эта проблема решается при помощи специального кода-разделителя (separator code) (в данном случае паузы) после последовательности точек и тире для каждой буквы. Другое решение состоит в том, чтобы построить систему кодирования так, чтобы никакой полный код символа не совпадал с началом (или префиксом) кода никакого другого символа. Такой код называется префиксным (prefix). В вышеприведенном примере A кодируется 0, а B 100, так что никакой другой символ не может иметь код, который начинается на 0 или 100.

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

Рисунок ниже изображает дерево Хаффмана для кода от A до H, показанного выше. Веса в вершинах дерева указывают, что дерево строилось для сообщений, где A встречается с относительной частотой 8, B с относительной частотой 3, а все остальные буквы с относительной частотой 1.

Имея дерево Хаффмана, можно найти код любого символа, если начать с корня и двигаться вниз до тех пор, пока не будет достигнута концевая вершина, содержащая этот символ. Каждый раз, как мы спускаемся по левой ветви, мы добавляем 0 к коду, а спускаясь по правой ветви, добавляем 1. (Мы решаем, по какой ветке двигаться, проверяя, не является ли одна из веток концевой вершиной, а также содержит ли множество при вершине символ, который мы ищем.) Например, начиная с корня на рисунке выше, мы попадаем в концевую вершину D, сворачивая на правую дорогу, затем на левую, затем на правую, затем, наконец, снова на правую ветвь; следовательно, код для D — 1011.

Чтобы раскодировать последовательность битов при помощи дерева Хаффмана, мы начинаем с корня и просматриваем один за другим биты в последовательности, чтобы решить, нужно ли нам спускаться по левой или по правой ветви. Каждый раз, как мы добираемся до листовой вершины, мы порождаем новый символ сообщения и возвращаемся к вершине дерева, чтобы найти следующий символ. Например, пусть нам дано дерево, изображенное на рисунке, и последовательность 10001010. Начиная от корня, мы идем по правой ветви (поскольку первый бит в строке 1), затем по левой (поскольку второй бит 0), затем опять по левой (поскольку и третий бит 0). Здесь мы попадаем в лист, соответствующий B, так что первый символ декодируемого сообщения — B. Мы снова начинаем от корня и идем налево, поскольку следующий бит строки 0. Тут мы попадаем в лист, изображающий символ A. Мы опять начинаем от корня с остатком строки 1010, двигаемся направо, налево, направо, налево и приходим в C. Таким образом, всесообщение было BAC.

Порождение деревьев Хаффмана

Если нам дан «алфавит» символов и их относительные частоты, как мы можем породить «наилучший» код? (Другими словами, какое дерево будет кодировать сообщения при помощи наименьшего количества битов?) Хаффман дал алгоритм для решения этой задачи и показал, что получаемый этим алгоритмом код — действительно наилучший код с переменной длиной для сообщений, где относительная частота символов соответствует частотам, для которых код строился. Здесь мы не будем доказывать оптимальностькодов Хаффмана, но покажем, как эти коды строятся

Алгоритм порождения дерева Хаффмана весьма прост. Идея состоит в том, чтобы упорядочить дерево так, чтобы символы с наименьшей частотой оказались дальше всего от корня. Начнем с множества терминальных вершин, содержащих символы и их частоты, как указано в исходных данных, из которых нам надо построить дерево. Теперь найдем два листа с наименьшими весами и сольем их, получая вершину, у которой предыдущие две являются левым и правым потомками. Вес новой вершины равен сумме весов ее ветвей. Исключим два листа из исходного множества и заменим их новой вершиной. Продолжим этот процесс. На каждом шаге будем сливать две вершины с самыми низкими весами, исключая их из множества и заменяя вершиной, для которой они являются левой и правой ветвями. Этот процесс заканчивается, когда остается только одна вершина, которая и является корнем всего дерева. Вот как было порождено дерево Хаффмана на рисунке выше:

Исходный набор листьев {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
Слияние {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
Слияние {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
Слияние {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
Слияние {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}
Слияние {(A 8) ({B C D} 5) ({E F G H} 4)}
Слияние {(A 8) ({B C D E F G H} 9)}
Окончательное слияние {({A B C D E F G H} 17)}

Алгоритм не всегда приводит к построению единственно возможного дерева, поскольку на каждом шаге выбор вершин с наименьшим весом может быть не единственным. Выбор порядка, в котором будут сливаться две вершины (то есть, какая из них будет левым, а какая правым поддеревом) также произволен.


Представление деревьев Хаффмана

В следующих упражнениях мы будем работать с системой, которая использует деревья Хаффмана для кодирования и декодирования сообщений и порождает деревья Хаффмана в соответствии с вышеописанным алгоритмом. Начнем мы с обсуждения того, как представляются деревья.
Листья дерева представляются в виде списка, состоящего из символа leaf (лист), символа, содержащегося в листе, и веса:

def isLeaf(obj):
    if car(obj)=='leaf':
        return True
    return False

def symbLeaf(x):
    return cdr(x)

def weightLeaf(x):
    return cddr(x)

Дерево в общем случае будет списком из левой ветви, правой ветви, множества символов и веса. Множество символов будет просто их списком, а не каким-то более сложным представлением. Когда мы порождаем дерево слиянием двух вершин, мы получаем вес дерева как сумму весов этих вершин, а множество символов как объединение множеств их символов. Поскольку наши множества представлены в виде списка, мы можем породить объединение при помощи процедуры append, определенной нами ранее.

def make_code_tree(left, right):
    return (left, right, append(symbols(left), symbols(right)), weight(left)+weight(right))

Если мы порождаем дерево таким образом, то у нас будут следующие селекторы:

def left_branch(tree):
    return car(tree)

def right_branch(tree):
    return cdr(tree)

def symbols(tree):
    if isLeaf(tree)==True:
        return symbLeaf(tree)
    return cddr(tree)

def weight(tree):
    if isLeaf(tree)==True:
        return weightLeaf(tree)
    return cdddr(tree)

Процедуры symbols и weight должны вести себя несколько по-разному в зависимости от того, вызваны они для листа или для дерева общего вида. Это простые примеры обобщенных процедур (generic procedures) (процедур, которые способны работать более, чем с одним типом данных).
Итак, ради интереса можете посмотреть на результат создания дерева tree=make_code_tree(('leaf', ('A', None), 8), (('leaf', ('B', None), 3), ('leaf', ('E', None), 1), ('B', 'E'), 4))


Процедура декодирования
Следующая процедура реализует алгоритм декодирования. В качестве аргументов она
принимает список из единиц и нулей, а также дерево Хаффмана.

def choose_branch(bit, branch):
    if bit==0:
        return left_branch(branch)
    elif bit==1:
        return right_branch(branch)
    else: print 'плохой бит -- CHOOSE-BRANCH'

def decode(bits, tree):
    def decode1(bits, cur_branch):
        if bits==None:
            return None
        next_branch=choose_branch(car(bits), cur_branch)
        if isLeaf(next_branch)==True:
            return (symbLeaf(next_branch), decode1(cdr(bits), tree))
        return decode1(cdr(bits), next_branch)
    return decode1(bits, tree)

Пример использования: decode((1, (0,(0, None))),tree), где tree мы создали с вами процедурой make_code_tree выше.
Процедура decode1 принимает два аргумента: список остающихся битов и текущую позицию в дереве. Она двигается «вниз» по дереву, выбирая левую или правую ветвь в зависимости от того, ноль или единица следующий бит в списке (этот выбор делается в процедуре choose_branch). Когда она достигает листа, она возвращает символ из него как очередной символ сообщения, присоединяя его посредством cons к результату декодирования остатка сообщения, начиная от корня дерева. Обратите внимание на проверку ошибок в конце choose_branch, которая заставляет программу протестовать, если во входных данных обнаруживается что-либо помимо единиц и нулей.

Множества взвешенных элементов

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

Мы представим множество листьев и деревьев как список элементов, упорядоченный
по весу в возрастающем порядке. Следующая процедура adjoinset для построения множеств работает так, что элементы сравниваются по своим весам, и никогда не бывает так, что добавляемый элемент уже содержится в множестве.

def adjoinSet(x, set):
    if set==None:
        return x
    if weight(x)<weight(car(set)):
        return (x, set)
    return (car(set), adjoinSet(x, cdr(set)))

Следующая процедура принимает список пар вида символ–частота, например ((A4) (B 2) (C 1) (D 1)), и порождает исходное упорядоченное множество листьев,готовое к слиянию по алгоритму Хаффмана:

def make_leaf_set(pairs):
    if pairs==None:
        return None
    pair=car(pairs)
    return adjoinSet(make_leaf(car(pair), cdr(pair)), make_leaf_set(cdr(pairs))) 

Пример использования: make_leaf_set(((('A', None), 4), ((('B', None), 2), ((('C', None), 1), ((('D', None), 1), None)))))

Ну вот и все, тут конечно еще есть над чем поработать, но идея я надеюсь вам ясна.
И практики хватило X)))

Используемая литература:

1. http://mitpress.mit.edu/sicp/