Изменения

Будем действовать согласно алгоритму выше;у нас число букв первоначального алфавита <tex>m</tex> равно 6.Если подставить значения <tex>n</tex> и <tex>m</tex> в формулу для оптимального кодирования <tex>m = n + k(n - 1)</tex> ,то получится что <tex>k</tex> не является целым.Но если увеличить число <tex>m</tex> на 1(добавлением фиктивной буквы "я" с весом 0),то можно подобрать целое <tex>k</tex> равное 2.

Возьмем <texmath>\mathrm{sum=0}</texmath>.На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <texmath>\mathrm{sum}</texmath> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота. В-итоге, <math>\mathrm{sum}</math> - число бит необходимое для кодирования этого текста

В-итоге,Сложность алгоритма <tex>sumO(n^2)</tex>-число бит необходимое для кодирования этого текста.

'''int''' <math>\mathrm{a[1..n] }</math> ''//исходный массив частот всех n символов,встречающихся в тексте" <math>\mathrm{sum}</math> =0; do sort for <math>\mathrm{i}</math> = 1..<math>\mathrm{n}</math> find(<math>\mathrm{min1}</math>,<math>\mathrm{min2}</math>) ''//отыскиваем индексы двух минимальных элементов массива swap(<math>\mathrm{a}</math>[1],<math>\mathrm{a}</math>[min1]) swap(<math>\mathrm{a}</math>[2],<math>\mathrm{a}</math>[min2]) ''//сортируем массив по возрастаниютеперь первые два элемента массива минимальные'' <math>\mathrm{a}</math>[2] = <math>\mathrm{a}</math>[1]+<math>\mathrm{a}</math>[2] <math>\mathrm{sum }</math> +=+ <math>\mathrm{a}</math>[2] <math>\mathrm{n}</math>-- delete(<math>\mathrm{a}</math>[1]) ''//убираем из массива ненужный элемент и больше его не рассматриваем'' while <math>\mathrm{n}</math> !=1 ''//пока не останется одна частота в массиве'' '''return''' <math>\mathrm{sum}</math> ==Построение кода Хаффмана==€В приведенном ниже псевдокоде предполагается,что <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> операций "слияния",в результате,которых образуется конечное дерево. HUFFMAN(<tex>C</tex>) struct Node //Звено дерева int <math>\mathrm{key}</math>, char <math>\mathrm{value}</math> //пара ключ и значение Node *left,*right <math>\mathrm{n}</math> = <math>\mathrm{|C|}</math> queue <char> <math>\mathrm{Q}</math> char <math>\mathrm{c}</math>[<math>\mathrm{n}</math>] , int <math>\mathrm{f}</math>[<math>\mathrm{n}</math>] //массив c содержит алфавит из n различных символов,массив f - соответствующий ему набор положительных целых весов. '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> <math>\mathrm{Q}</math>.insert(<math>\mathrm{f}</math>[<math>\mathrm{i}</math>],<math>\mathrm{c}</math>[<math>\mathrm{i}</math>]) '''for''' <math>\mathrm{i}</math> = 1 '''to''' <math>\mathrm{n}</math> - 1 (<math>\mathrm{min1}</math>,<math>\mathrm{x}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.left = <math>\mathrm{x}</math> (<math>\mathrm{min2}</math>,<math>\mathrm{y}</math>) = <math>\mathrm{Q}</math>.extract_min() <math>\mathrm{z}</math>.right = <math>\mathrm{y}</math> <math>\mathrm{sum}</math> = <math>\mathrm{min1}</math> + <math>\mathrm{min2}</math> <math>\mathrm{Q}</math>.insert(<math>\mathrm{sum}</math>,<math>\mathrm{z}</math>) '''return''' <math>\mathrm{z}</math>   Алгоритм работает за <tex> {O(n\log{n}}) </tex> для алфавита из <math>\mathrm{n}</math> символов.