Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 114
Текст из файла (страница 114)
использовать для их хранения как можно меньше места. Очевидный способ компактно скомпоновать данные — изменять длину строк, используемых для их хранения, так чтобы более короткие строки хранили часто используемые символы, а более длинные строки — редко используемые символы. И здесь возникает проблема; если строки, представляющие разные символы, имеют разную длину, то как узнать, где заканчивается строка одного символа и начинается строка другого? Например, если Ь представлено как 101, е как 11, а как 10, у как 1011 и ш как 110, то строка 1011110 представляет беа или уш? Определим однозначно декадируемый кад для языка как такое множество, что каждая строка в языке может быть задана однозначно как конкатенация элементов С.
В этом случае строки из единиц и нулей, представляющие элементы из А, будут нашим кодом. Если эти строки образуют однозначно декодируемый код, то, по крайней мере, разделяя строки на элементы, представляющие А, мы знаем, что представление однозначно и, следовательно, декодированные слова правильные. Хотелось бы это как-то улучшить. Определим код С как префиксный код, если он обладает тем свойством, что никакой элемент кода не может быть начальной строкой другого элемента кода. Таким образом, прочитав строку из единиц и нулей, представляющую символ из А, мы знаем, что это искомый символ, а не начало другого символа. Поэтому следующие 1 или 0 должны начинать строку для следующего символа, который декодируется.
Например, если РЯЗДЕЛ 15.3. Взвешенные деревья 639 строки 111, 1011, 1001, 110 и 01 представляют в пятибуквенном алфавите соответственно буквы а, е, г, о и и и в качестве первых трех знаков строки имеются цифры 110, это означает представление буквы о, поскольку никакая другая буква не начинается с этих цифр. Аналогично, если следующие три цифры 011, это означает, что 01 представляет букву и, а 1 — начало следующей буквы. Рассмотрим бинарное дерево с листьями Гы Гз, Пз, ~4, Га и га, изобРаженное на Рис. !5.23.
Если рассматривать путь от корня дерева к лю- О 1 бому из листьев, то каждое ребро вдоль пути должно вести к правому или левому сыну предыдущей вершины. Если ребро ведет к левому г, д 1 г, сыну, обозначим его через О, а если к правому сыну, то пометим его 1. Поскольку путь к а 3 5 е листу пг есть путь к левому сыну, а затем к Р-, 1д.гг другому левому сыну, то путь к пг обозначаем через 00.
Аналогично пути к пз, пз, и4, пз и ее обозначаются через 010, 011, 10, 110 и 111. Строку, соответствующую данному листу, назовем путевым кодом. Заметим, что строки, соответствующие этим листьям, образуют префиксный код. Строка, соответствующая каждому листу, определяется однозначно, так как к каждому листу ведет единственный путь. Обобщая вышеизложенное, приходим к следующей теореме.
Доказательство оставляем читателю. ТЕОРЕМА 16.14. В любом бинарном дереве путевые коды для листьев дерева являются префиксным кодом. Предположим, что имеется бинарное дерево и для каждого символа в алфавите А, который требуется представить с помощью двоичной строки, на дереве имеется лист. Присвоим каждой букве алфавита А путевой код соответствующего листа на бинарном дереве. Таким образом, если буквы а, е, г, о, и и ш связаны соответственно с листьями пы пз, ез, ие, ьз и ее в упомянутом выше дереве, то буквам а, е, з, о, и и ш соответствуют строки 00, 010, 011, 10, 110 и 111.
Первоначальная формулировка задачи содержала требование, чтобы часто встречющиеся символы имели более короткие строки. В рамках изложенного выше метода это означает, что часто встречающимся символам должен соответствовать более короткий путь от корня или, что равносильно, они должны находиться на более низком уровне. Для того чтобы оценить, насколько близки мы от цели поставить в соответствие часто встречающимся буквам более короткие строки, т.е. минимизировать коды, необходим некоторый критерий.
Предположим, что каждая буква а, в алфавите символов А появляется с относительной частотой 1; и представляющая ее двоичная строка имеет длину 1,. Тогда величина п ш = 1г1'г + 1з1'з+ 1з1з+ 1414+ + 1~У» =,> 1*Л а=! называется весом кода. Если листья взвешенного дерева представляют знаки кода, вес листа равен частоте появления буквы, а расстояние от корня до вершины равно длине двоичного кода для символа в листе. Определим вес дерева как 640 ГЛАВА 15.
Деревья величину и ш =1гЛ+1зЬ+1зУз+14У4+ "+1»Л = ~~' 1Л. ьм В более общем виде вес дерева определяется как 1!ш1 + 12шз + 1зшз + 14ш + ' ' ' + 1еше = ~~~ 1гшч где ш, — вес, приписанный вершине о,, и 1г — длина пути от корня до вершины. Данное понятие не следует путать с понятием взвешенного графа, включающего деревья, где вес приписывается ребрам. Эти вопросы мы обсудим в разделе 15.6. Чем меньше вес дерева, тем в большей степени достигнута поставленная цель. Таким образом, чтобы найти наилучший код для минимизации данных, необходимо найти код с минимальным весом.
Процесс построения такого дерева называется алгоритмом Хаффмама. Код, приписываемый символам согласно их путевому коду, называется кодом Хаффмана. Прежде чем излагать алгоритм, следует разобраться в механизме его работы. Предположим, имеются следующие буквы и соответствующие им частоты: 3 Для начала разместим частоты в возрастающем по- Л рядке: (1, 2, 3, 5, 7, 8, 10).
Затем формируем дерево, используя две буквы с наименьшими частотами в качестве верь Ф шин и сумму частот в качестве их родителя. Помещаем Рис. 15.24 0 на ребре к левому сыну и 1 на ребре к правому сыну, после чего получаем дерево, изображенное на рис. 15.24. В списке частот заменяем значения двух наимень0 ших частот их суммой, после чего имеем (3, 3, 5, 7, 8, 10).
Если бы полученная сумма оказалась больше одной или О 1 нескольких частот в списке, его надо было бы отсортировать так, чтобы частоты снова располагались в возрастающем порядке. Опять выбираем две вершины или деревья в соответствии с наименьшими числами в списке частот и формируем дерево с этими вершинами или деревьями в качестве сыновей и их суммой в качестве родителя. В данном случае это дерево со значением 3 и буква ш со значением 3 в качестве сыновей и их суммой 6 в качестве родителя.
РАЗДЕЛ 15.3. Взвешенные деревья 641 Помещаем 0 на ребре к левому сыну и 1 на ребре к правому сыну, после чего получаем граф (рис. 15.25). Теперь заменим в списке частот значения двух наименьших частот их суммой, 6, и расположим значения в возрастающем порядке. В результате получим список 11 (5,6,7,8, 10). Во всех случаях значения вершин или дере- О 1 вьев, использованных в качестве сыновей, удаляются из списка частот и из строящегося дерева. Мы формируем я дерево, выбирая две вершины или два дерева с наимень- О 1 шими числами в списке частот и используя их как сыновей, а их сумму в качестве частоты родителя. В данном случае это вершина я со значением 5 и дерево со значением 6. Помещаем 0 на ребро к левому сыну и 1 на ребро к правому сыну, после чего получаем дерево, изображенное на рис.
15.26. В списке частот опять заменяем значения двух наименьших частот их суммой, 11, и располагаем значения частот в возрастающем порядке, после чего получаем список (7,8,10,11). Продолжая процесс, получаем следующие деревья и списки частот: рис. 15.27 (10, 11, 15) и рис.
!5.28 (15, 21). Рис. 15.25 21 Л Л Рис. 15.27 Рис. 15.28 Наконец, соединяем два оставшихся дерева, поместив 0 на ребро к левому сыну, 1 на ребро к правому сыну, в результате получаем дерево, изображенное на рис. 15.29. Рис. 15.29 Помещать сумму в корень нет необходимости. Заметим, что числами кода Хаффмана для а, е, ш, 1с, га, 77 и % являются ОО, 10, 1111, 01, 110, 11101 и 11100 соответственно. Ниже представлен алгоритм Хаффмана построения дерева для символов зы зз,... з„, имеющих соответствующие частоты 1ы 7з,..., 1„.
642 ГЛАВА 15. Деревья Алгоритм Хаффмана ((вг,,Гг), (ез,,Гз),..., (е„, 7"„)) (1) Расположить частоты в возрастающем порядке в таблице частот. (2) Если 7; и 7", — две наименьшие частоты, то сформировать бинарное дерево с з, и з, в качестве сыновей, где з; — левый, а 7;+ 71 — частота РодителЯ. Поместить 0 на ребро к левому сыну, а 1 — на ребро к правому сыну, (3) Удалить 7", и Л из таблицы частот и заменить суммой 7', + г',.
(4) Снова расположить частоты в возрастающем порядке. (5) Удалить две наименьшие частоты из таблицы частот и сформировать дерево, используя в качестве сыновей символы или деревья, соответствующие этим частотам, когда меньший символ или дерево — левый, а сумма их частот — частота родителя. Если какой-либо из сыновей — дерево, удалить метку его частоты из построенного дерева. (б) Заменить значение двух наименьших частот их суммой.
(7) Повторять шаги 4-7, пока в таблице частот не останется только один элемент. (8) Удалить частоту из корня дерева и из таблицы частот. (9) Сформировать код Хаффмана для элемента, составляя строку из единиц и нулей на ребрах пути из корня к заданному элементу. Рассмотрим вторую из упомянутых выше задач с таким же решением. Предположим, имеется и элементов данных и известна частота использования каждого из них. Требуется сохранить их как листья бинарного дерева так, чтобы наиболее часто используемые элементы были более доступны при обратном поиске.
Но это означает, что наиболее часто используемым элементам должны соответствовать самые короткие пути от корня. Это как раз то, что делалось до сих пор, поскольку наиболее часто используемые символы имеют самые короткие двоичные строки и, следовательно, самые короткие пути от корня. ПРИМЕР 16.16. Предположим, имеются следующие буквы и их частоты; Построим такое бинарное дерево, чтобы наиболее часто используемые элементы были возможно ближе расположенны к корню.
Более точно, требуется найти такое дерево, что вес дерева ш = 11Л + 1272 + 13УЗ + 1414 + ' ' ' + (иУи Х~~ (~Л а=1 РАЗДЕЛ И.З. Взвешенные деревья 643 минимален, где 1, и 1г — уровень и частота заданного элемента. Сначала упорядочим частоты, приведенные в списке частот (5,10,13,17,25,30). Воспользовавшись приведенным выше алгоритмом, получаем следующие деревья и списки частот: рис. 15.30, (13, 15, 17, 25, 30); рис. 15.31 (17, 25, 28, 30); рис. !5.32 (28, 30, 42); рис.
15.33 (42,58). Е ~~0 ~! 23 42 О 1 О 1 8 О 1 А В с С Рис. 15.30 г С Рис. 15.31 Рис. 15.32 В заключение объединяем два дерева и формируем искомое дерево, которое изображено на рис. 15.34. 53 О/~ 1 А В Р С Рис, 15.33 Рис. 15.34 Теперь необходимо показать, что дерево Хаффмана — это дерево с минимальным весом. Начнем с доказательства серии лемм. ЛЕММА 16.16. Для заданного множества из п символов и их частот существует бинарное дерево минимального веса с символами в качестве листьев. в 11 Л + 12 з 2 + 1313 + 14 14 + ' ' ' + 1п.7п = ~ 1а Л й=1 и выберем дерево, которое обеспечивает наименьшее значение. ЛЕММА 16.17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
