Построение ОНК по методике Хаффмена

Решение.

Таблица 4.2 – Оптимальный код неравновероятных букв.

ai	pi	Кодовое слово после разбиения	Знаков	lipi
	0,5		-	-	-	-	-		0,5
	0,25			-	-	-	-		0,5
	0,098					-	-		0,392
	0,052					-	-		0,208
	0,04					-	-		0,16
	0,03						-		0,15
	0,019								0,114
	0,011								0,066

Хаффмен предложил следующий метод построения ОНК:

1) Символы первичного алфавита выписываются в порядке убывания вероятностей.

2) Последние n₀ символов, где 2 £ n₀ £ m и N - n₀/m - 1 - целое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединяемых символов.

3) Последние символы с учетом образованного символа вновь объединяют и получают новый, вспомогательный, символ.

4) Опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного символа и т. д. До тех пор, пока вероятности m оставшихся символов после N - n₀/m - 1-го выписывания не дадут в сумме 1.

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

Пример: Построить методом Хаффмена оптимальный код для алфавита со следующим распределением вероятностей появления букв в тексте: A = 0,5; B = 0,15;

C = 0,12; D = 0,1; E = 0,04; F = 0,04; G = 0,03; H = 0,02.

Решение. Сначала находят буквы с наименьшими вероятностями 0,02 (H) и 0,03 (G), затем проводят от них линию к точке, в которой вероятность появления буквы G равна 0,05. Затем берут две наименьшие вероятности 0,04 (F) и 0,04 (E) и получают новую точку с вероятностью 0,08. Теперь наименьшими вероятностями обладают точки, соответствующие вспомогательным символам с вероятностями 0,05 и 0,08. Соединяем их линией с новой точкой, соответствующей вспомогательному символу с вероятностью 0,13. Продолжаем в том же духе до тех пор, пока линия от основных и вспомогательных символов не сольются в точке, дающую суммарную вероятность, равную 1. Обозначим каждую верхнюю линию (см. рисунок) цифрой 1, а нижнюю - цифрой 0. Получим ОНК, который для каждого слова представляет собой последовательность нулей и единиц, которые встречаются по пути к данному слову от конечной точки (1,00). Полученные коды представлены в таблице

Таблица 4.3 – Двоичный код Хаффмена для 8-и сообщений

Буква	Вероятность	ОНК	Число знаков в кодовом слове	pili
A B C D E F G H	0,50 0,15 0,12 0,10 0,04 0,04 0,03 0,02	0 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0		0,50 0,45 0,36 0,30 0,20 0,20 0,15 0,10

Пример: Построить код Хаффмена для передачи сообщений при помощи трех частот f₁, f₂, f₃, если символы первичного алфавита встречаются в сообщениях со следующими вероятностями: А = 0,24; Б = 0,18; В = 0,38; Г = 0,1; Д = 0,06; Е = 0,02; Ж = 0,02.

Дата добавления: 2015-08-31