Изменения
→Построение кода Хаффмана
==Построение кода Хаффмана==
В приведенном ниже псевдокоде предполагается,что <tex>C</tex> - множество,состоящее из <tex>n</tex> символов,и что каждый из символов <tex>c \in C</tex> - объект с определенной частотой <tex>f(c)</tex>.В алгоритме строится оптимальное дерево <tex>T</tex>,соответствующее оптимальному коду,причем построение идет в восходящем направлении.Процесс построения начинается с множества,состоящего из <tex>|C|</tex> листьев,после чего последовательно выполняется <tex>|C|-1</tex> операций "слияния",в результате,которых образуется конечное дерево.Для идентификации двух наименее часто встречающихся объектов,подлежащих слиянию,используется очередь с приоритетами <tex>Q</tex>,ключами в которой являются частоты <tex>f</tex>.В результате слияния двух объектов образуется новый объект,частота появления которого является суммой частот объединенных объектов:
HUFFMAN(<tex>C</tex>)
1 <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math>
2 <math>\mathrm{Q}</math> = <math>\mathrm{C}</math>
3 '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 4 '''do''' Выделить память для узла <math>\mathrm{z}</math> 5 <math>\mathrm{x}</math> = Extract_Min(<math>\mathrm{Q}</math>) //Extract_Min - изъятие из множества наименьшего элемента 6 5 left[<math>\mathrm{z}</math>] = <math>\mathrm{x}</math> 7 6 <math>\mathrm{y}</math> = Extract_Min(<math>\mathrm{Q}</math>) 8 7 right[<math>\mathrm{z}</math>] = <math>\mathrm{y}</math> 9 8 <math>\mathrm{f}</math>[<math>\mathrm{z}</math>] = <math>\mathrm{f}</math>[<math>\mathrm{x}</math>] + <math>\mathrm{f}</math>[<math>\mathrm{y}</math>] 10 9 Insert(<math>\mathrm{Q}</math>, <math>\mathrm{z}</math>) 11 10 '''return''' Extract_Min(<math>\mathrm{Q}</math>) //Возврат корня дерева
В строке <tex>'''2</tex> ''' инициализируется очередь с приоритетом <tex>Q</tex>,состоящая из элементов множества <tex>C</tex>.Цикл '''for''' в строках '''3 - 109''' поочередно извлекает по два узла,<tex>x</tex> и <tex>y</tex>,которые характеризуются в очереди с наименьшими частотами,и заменяет их в очереди с новым узлом <tex>z</tex>,представляющим объединение упомянутых выше элементов.Частота появления <tex>z</tex> вычисляется в строке '''98''' как сумма частот <tex>x</tex> и <tex>y</tex>.Узел <tex>x</tex> является левым дочерним узлом <tex>z</tex>, а <tex>y</tex> - его правым дочерним узлом.(Этот порядок является произвольным;перестановка левого и правого дочерних узлов приводит к созданию другого кода с той же стоимостью.) После <tex>n-1</tex> объединений в очереди остается один узел - корень дерева кодов,который возвращается в строке '''1110'''.
Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.
