1632
правки
Изменения
м
sortdo for <math>\mathrm{i}</math> = 1..<math>\mathrm{n}</math> find(<math>\mathrm{amin1}</math>,<math>\mathrm{min2}</math>) ''//сортируем массив по возрастанию''отыскиваем индексы двух минимальных элементов массива doswap(<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>[12]= <math>\mathrm{a}</math> [1] + <math>\mathrm{a[2]}</math>[2] <math>\mathrm{sum}</math> +=+ <math>\mathrm{a[2]}</math>[2] <math>\mathrm{n}</math>-- delete(<math>\mathrm{a[1]}</math>[1]) ''//убираем из массива ненужный элемент и больше его не рассматриваем'' while <math>\mathrm{n}</math> != 1 ''//пока не останется одна частота в массиве''
rollbackEdits.php mass rollback
Имеются частоты символов,встречающихся в исходном тексте.Необходимо подсчитать суммарное число бит,необходимое для кодирования этого текста.
Возьмем <texmath>\mathrm{sum=0}</texmath>.На каждом шаге выбираем две наименьшие частоты,объединяем их сумму в одну частоту и добавляем в список вместо двух исходных.Новую частоту прибавляем к <texmath>\mathrm{sum}</texmath> с присваиванием.Шаги заканчиваются тогда,когда в списке останется только одна частота.
В-итоге,<texmath>\mathrm{sum}</texmath>-число бит необходимое для кодирования этого текста Сложность алгоритма <tex>O(n^2)</tex>.
Псевдокод алгоритма:
'''int''' <math>\mathrm{a[1..n]}</math> ''//исходный массив частот всех n символов,встречающихся в тексте"
<math>\mathrm{sum}</math> = 0
'''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> символов.
