АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритм Хаффмана. Код Хаффмана – это свободный от префикса код, который может давать самую короткую среднюю длину кода для данного входного алфавита

Читайте также:
  1. IV. Алгоритм действий командира (начальника) при увольнении военнослужащего в связи с невыполнением им условий контракта
  2. LZW-модификация алгоритма Лемпеля-Зива
  3. Zip–модификация алгоритма Лемпеля-Зива
  4. А.3.3. Алгоритм медикаментозного лікування
  5. АЛГОРИТМ
  6. Алгоритм
  7. Алгоритм
  8. Алгоритм
  9. Алгоритм 1.11. Пошук невідкладних дій (перша медична допомога) симптоматичної допомоги при гострих струєннях.
  10. Алгоритм 1.4. Діагностичний і лікувальний (перша медична допомога) пошук при гіпертонічній кризі
  11. Алгоритм 2.4. Транспортна іммобілізація
  12. Алгоритм First Come First Served (FCFS)

Код Хаффмана – это свободный от префикса код, который может давать самую короткую среднюю длину кода для данного входного алфавита. Заметим, что самая короткая средняя длина кода для конкретного алфавита может быть значительно больше энтропии алфавита источника. Алгоритм кодирования Хаффмана может применяться для преобразования между двумя любыми алфавитами, чаще всего его используют для преобразования произвольного алфавита в двоичный [2].

Рассмотрим работу алгоритма Хаффмана на примере.

Пример. Построить двоичный код Хаффмана для представленного в таблице алфавита. В таблице использованы следующие обозначения Xi – i-тый символ алфавита, Р(Xi) – вероятность появления символа Xi.

Xi а b с d
Р(Xi) 0,12 0,3 0,38 0,2

 
 

Упорядочим символы алфавита по убыванию вероятностей их появления и сопоставим их ветвям двоичного дерева.

Два входа с самой низкой относительной частотой объединим в новую ветвь. Вероятность, соответствующую этой ветви вычислим как сумму вероятностей объединенных ветвей. После объединения переупорядочим все ветви дерева таким образом, чтобы в дереве сохранялась убывающая вероятность ветвей. В случае, когда необходимо построить выходной алфавит не двоичным, а например m-ичным, то необходимо объединять ветви дерева по m штук, которым соответствуют наименьшие значения вероятностей.

 

 

 

 


 
 

Будем продолжать этот процесс до достижения корня дерева.

 

После формирования всего дерева пометим ветви, выходящие из всех вершин символами “0” и “1”. Помечать ветви дерева можно произвольным образом, для определенности ветвь, идущую вверх будем помечать символом “1”, а ветвь, идущую вниз – символом “0”.

После обозначения вершин пройдем все возможные пути по дереву от вершины (крайнее правое положение) дерева до его каждой выходной ветви (крайнее левой положение), запоминая встретившиеся двоичные символы. Полученные последовательности будут являться кодами символов входного алфавита.


Значения, характеризующие построенный код Хаффмана, сведем в таблицу следующего вида. В первом столбце перечислим все символы алфавита (Xi); во втором столбце расположим соответствующие вероятности появления символов входного алфавита Р(Xi); в третьем столбце запишем кодовые слова, соответствующие символам входного алфавита; в последнем – четвертом столбце поместим значения .

Xi Р(Xi) Код Длина кода, , бит
с 0,38     0,38
b 0,3     0,6
d 0,2     0,6
a 0,12     0,36

 

Среднюю длину кода вычислим по формуле:

.

Результирующее значение =1,94 бит на знак, что не означает, что для передачи одного символа необходимо передавать нецелое число бит, а означает, что для передачи 100 входных символов из алфавита мощностью 4 потребуется примерно 194 бита.


1 | 2 | 3 | 4 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)