Метод Хаффмана

Поиск оптимального кода по этому методу тоже начинают с построения рабочей таблицы (первая процедура), в которой в крайней справа и соседней с ней колонках, как и в предыдущем случае, размещают символы естественного алфавита источника информации и их вероятности в порядке их убывания. Старые символы, обозначающие репертуар источника информации, как и раньше, разбивают на две группы с равными суммарными вероятностями входящих в них символов. Но здесь (в технологии Хаффмана) это делают путём последовательного (из таблицы видно, каким образом) образования промежуточных вспомогательных групп с из символов (и образованных накануне групп) с наименьшими вероятностями – групп-алфавитов с более равномерным распределением вероятностей.

Рабочая таблица метода Хаффмена

Состо-яния	Вероят-ности								Кодовое слово
							0,58
						0,42	0,42
					0,32	0,32
				0,26	0,26	0.26
S1	0,22	0,22	0,22	0,22	0,22				01
S2	0,20	0,20	0,20	0,20	0,20				00
S3	0,16	0,16	0,16	0,16					111
S4	0,16	0,16	0,16	0,16					110
S5	0,10	0,10	0,16						100
S6	0,10	0,10	0,10						1011
S5	0,04	0, 06							10101
S6	0,02								10100

Из таблицы видно, что вновь образуемые группы (в таблице для них указаны только вероятности их символов) каждый раз выстраиваются в новой колонке по убыванию вероятностей, а в новой колонке снова образуется вспомогательная группа. Делается это до тех пор, пока не останется двух групп состояний кодируемого источника, с приблизительно одинаковой вероятностью образующих их состояний. В последней колонке – контрольная цифра, которая выражает, что последний алфавит – ансамбль.

На этом первая процедура метода, который ещё называют методом промежуточных группировок, заканчивается.

Вторая процедура – построение кодового дерева Хаффмана.

В ходе её графически воспроизводится процесс последовательного разделения общей (равной единице) суммарной вероятности реализации, хотя бы одного старого символа в рамках реализации каждой из групп. Это распределение прослеживается в порядке, обратном порядку образования групп. Ниже такое дерево показано и оно означает, что для реализации любого символа старого алфавита вначале должна реализоваться одна из двух полученных в итоге разбиения и приблизительно равновероятных групп, групп.

Именно это символизирует первое «прикорневое» разветвление дерева, а далее все ветви помечены взятыми из предпоследней колонки рабочей таблицы вероятностями реализации состояний источника из соответствующих групп.

Последующие разветвления с соответствующими цифрами из расположенных всё левее и левее колонок показывают, как распределяются между меньшими группами и отдельными символами старого алфавита те вероятности, которые приходились на предыдущие более крупные группы. При этом, если при первом ветвлении правой оказалась ветвь с большей вероятностью, то и при всех последующих разветвлениях такая ветвь всегда должна быть правой.

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

Последний этап формирования оптимального кода методом Хаффмана – построение кодовых слов для каждого символа старого алфавита, заполнение последней колонки рабочей таблицы.

Кодовое дерево Хаффмана

0,42 0,58

Дата добавления: 2015-06-27