Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 38
Текст из файла (страница 38)
Иногда полезно использовать и коды с переменной длиной(variable-length), в которых различные символы могут представляться различным числомбитов. Например, азбука Морзе не для всех букв алфавита использует одинаковое числоточек и тире. В частности, E, наиболее частая (в английском) буква, представляется спомощью одной точки. В общем случае, если наши сообщения таковы, что некоторыесимволы встречаются очень часто, а некоторые очень редко, то мы можем кодироватьсвои данные более эффективно (т. е.
с помощью меньшего числа битов на сообщение),если более частым символам мы назначим более короткие коды. Рассмотрим следующийкод для букв с A по H:AB0100CD10101011EF11001101GH11101111С таким кодом то же самое сообщение преобразуется в строку100010100101101100011010100100000111001111В этой строке 42 бита, так что она экономит более 20% места по сравнению с приведенным выше кодом с фиксированной длиной.164Глава 2. Построение абстракций с помощью данныхОдна из сложностей при работе с кодом с переменной длиной состоит в том, чтобыузнать, когда при чтении последовательности единиц и нулей достигнут конец символа.В азбуке Морзе эта проблема решается при помощи специального кода-разделителя(separator code) (в данном случае паузы) после последовательности точек и тире длякаждой буквы. Другое решение состоит в том, чтобы построить систему кодированиятак, чтобы никакой полный код символа не совпадал с началом (или префиксом) коданикакого другого символа.
Такой код называется префиксным (prefix). В вышеприведенном примере A кодируется 0, а B 100, так что никакой другой символ не может иметькод, который начинается на 0 или 100.В общем случае можно добиться существенной экономии, если использовать кодыс переменной длиной, использующие относительные частоты символов в подлежащихкодированию сообщениях. Одна из схем такого кодирования называется кодированиемпо Хаффману, в честь своего изобретателя, Дэвида Хаффмана. Код Хаффмана можетбыть представлен как бинарное дерево, на листьях которого лежат кодируемые символы.В каждом нетерминальном узле находится множество символов с тех листьев, которыележат под данным узлом. Кроме того, каждому символу на листе дерева присваиваетсявес (представляющий собой относительную частоту), а каждый нетерминальный узелимеет вес, который равняется сумме весов листьев, лежащих под данным узлом.
Весане используются в процессе кодирования и декодирования. Ниже мы увидим, как ониоказываются полезными при построении дерева.Рисунок 2.18 изображает дерево Хаффмана для кода от A до H, показанного выше.Веса в вершинах дерева указывают, что дерево строилось для сообщений, где A встречается с относительной частотой 8, B с относительной частотой 3, а все остальные буквыс относительной частотой 1.Имея дерево Хаффмана, можно найти код любого символа, если начать с корня идвигаться вниз до тех пор, пока не будет достигнута концевая вершина, содержащаяэтот символ. Каждый раз, как мы спускаемся по левой ветви, мы добавляем 0 к коду, аспускаясь по правой ветви, добавляем 1. (Мы решаем, по какой ветке двигаться, проверяя, не является ли одна из веток концевой вершиной, а также содержит ли множествопри вершине символ, который мы ищем.) Например, начиная с корня на картине 2.18, мыпопадаем в концевую вершину D, сворачивая на правую дорогу, затем на левую, затемна правую, затем, наконец, снова на правую ветвь; следовательно, код для D — 1011.Чтобы раскодировать последовательность битов при помощи дерева Хаффмана, мыначинаем с корня и просматриваем один за другим биты в последовательности, чтобырешить, нужно ли нам спускаться по левой или по правой ветви.
Каждый раз, как мыдобираемся до листовой вершины, мы порождаем новый символ сообщения и возвращаемся к вершине дерева, чтобы найти следующий символ. Например, пусть нам данодерево, изображенное на рисунке, и последовательность 10001010. Начиная от корня,мы идем по правой ветви (поскольку первый бит в строке 1), затем по левой (посколькувторой бит 0), затем опять по левой (поскольку и третий бит 0).
Здесь мы попадаем влист, соответствующий B, так что первый символ декодируемого сообщения — B. Мыснова начинаем от корня и идем налево, поскольку следующий бит строки 0. Тут мы попадаем в лист, изображающий символ A. Мы опять начинаем от корня с остатком строки1010, двигаемся направо, налево, направо, налево и приходим в C.
Таким образом, всесообщение было BAC.2.3. Символьные данные165{A B C D E F G H} 17{B C D E F G H} 9A 8{B C D} 5{C D} 2B 3C 1D 1{E F G H} 4{E F} 2E 1{G H} 2F 1G 1H 1Рис. 2.18. Дерево кодирования по Хаффману.Порождение деревьев ХаффманаЕсли нам дан «алфавит» символов и их относительные частоты, как мы можем породить «наилучший» код? (Другими словами, какое дерево будет кодировать сообщенияпри помощи наименьшего количества битов?) Хаффман дал алгоритм для решения этойзадачи и показал, что получаемый этим алгоритмом код — действительно наилучший кодс переменной длиной для сообщений, где относительная частота символов соответствует частотам, для которых код строился. Здесь мы не будем доказывать оптимальностькодов Хаффмана, но покажем, как эти коды строятся42 .Алгоритм порождения дерева Хаффмана весьма прост.
Идея состоит в том, чтобыупорядочить дерево так, чтобы символы с наименьшей частотой оказались дальше всегоот корня. Начнем с множества терминальных вершин, содержащих символы и их частоты, как указано в исходных данных, из которых нам надо построить дерево. Теперьнайдем два листа с наименьшими весами и сольем их, получая вершину, у которойпредыдущие две являются левым и правым потомками. Вес новой вершины равен сумме весов ее ветвей. Исключим два листа из исходного множества и заменим их новойвершиной. Продолжим этот процесс.
На каждом шаге будем сливать две вершины с самыми низкими весами, исключая их из множества и заменяя вершиной, для которой ониявляются левой и правой ветвями. Этот процесс заканчивается, когда остается толькоодна вершина, которая и является корнем всего дерева. Вот как было порождено деревоХаффмана на рисунке 2.18:42 Обсуждениематематических свойств кодов Хаффмана можно найти в Hamming 1980.Глава 2. Построение абстракций с помощью данных166Исходный набор листьевСлияниеСлияниеСлияниеСлияниеСлияниеСлияниеОкончательное слияние{(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 (лист),символа, содержащегося в листе, и веса:(define (make-leaf symbol weight)(list ’leaf symbol weight))(define (leaf? object)(eq? (car object) ’leaf))(define (symbol-leaf x) (cadr x))(define (weight-leaf x) (caddr x))Дерево в общем случае будет списком из левой ветви, правой ветви, множества символов и веса. Множество символов будет просто их списком, а не каким-то более сложным представлением.
Когда мы порождаем дерево слиянием двух вершин, мы получаем вес дерева как сумму весов этих вершин, а множество символов как объединениемножеств их символов. Поскольку наши множества представлены в виде списка, мыможем породить объединение при помощи процедуры append, определенной нами вразделе 2.2.1:(define (make-code-tree left right)(list leftright(append (symbols left) (symbols right))(+ (weight left) (weight right))))Если мы порождаем дерево таким образом, то у нас будут следующие селекторы:2.3. Символьные данные167(define (left-branch tree) (car tree))(define (right-branch tree) (cadr tree))(define (symbols tree)(if (leaf? tree)(list (symbol-leaf tree))(caddr tree)))(define (weight tree)(if (leaf? tree)(weight-leaf tree)(cadddr tree)))Процедуры symbols и weight должны вести себя несколько по-разному в зависимостиот того, вызваны они для листа или для дерева общего вида. Это простые примерыобобщенных процедур (generic procedures) (процедур, которые способны работать более,чем с одним типом данных), о которых мы будем говорить намного более подробно вразделах 2.4 и 2.5.Процедура декодированияСледующая процедура реализует алгоритм декодирования.
В качестве аргументов онапринимает список из единиц и нулей, а также дерево Хаффмана.(define (decode bits tree)(define (decode-1 bits current-branch)(if (null? bits)’()(let ((next-branch(choose-branch (car bits) current-branch)))(if (leaf? next-branch)(cons (symbol-leaf next-branch)(decode-1 (cdr bits) tree))(decode-1 (cdr bits) next-branch)))))(decode-1 bits tree))(define (choose-branch bit branch)(cond ((= bit 0) (left-branch branch))((= bit 1) (right-branch branch))(else (error "плохой бит -- CHOOSE-BRANCH" bit))))Процедура decode-1 принимает два аргумента: список остающихся битов и текущуюпозицию в дереве.
Она двигается «вниз» по дереву, выбирая левую или правую ветвь взависимости от того, ноль или единица следующий бит в списке (этот выбор делается впроцедуре choose-branch). Когда она достигает листа, она возвращает символ из негокак очередной символ сообщения, присоединяя его посредством cons к результату декодирования остатка сообщения, начиная от корня дерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
