новая папка 1 / 565004

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

_______________________________________________________________________________

4.2. Методические указания к заданию 3.2

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

Рассмотрим принцип построения таких кодов методами Шеннона-Фано и Хаффмана [2, 3]. Оба этих кода основываются на статистических свойствах источника сообщений и ставят в соответствие часто встречающимся символам алфавита короткие кодовые комбинации.

Рис. 4.2.1. Абсолютные частоты появления букв в книге [1]

Из-за того, что разным символам алфавита соответствуют кодовые комбинации разной длины, такие коды называют неравномерными.

В качестве примера возьмем сообщение: «ИНН 637322757237». Данный текст содержит избыточность, которую невозможно устранить с помощью метода RLE. Избыточность определяется по формуле:

	L 1	H	100%	,
		n

где H - энтропия сообщения;

n - длина кодовой комбинации при равномерном кодировании. Энтропия сообщения вычисляется по формуле:

	N	,
H	pi log2 pi
	i 1

где N - объем алфавита источника (для русского алфавита N =33);

pi - относительная частота (вероятность) появления символа в сообщении. Относительная частота встречаемости символа определяется как отноше-

ние абсолютной частоты появления символа в сообщении к общей длине сообщения (числу символов в сообщении):

pi mi ,

где i - абсолютная частота (частость) встречаемости i-ого символа алфавита источника; m – число символов в сообщении.

В данном случае энтропия сообщения равна:

11

_______________________________________________________________________________

H			4	log2					4			2			3	log2	3			2	log2	2		4	1	log2	1		2,781 бит/символ,
			16						16			16					16		16			16		16			16
где p1				4							1	- относительная частота появления символа «7»;
				16					4
p2		p3		3				- относительная частота появления символов «2» и «3»;
			16
p4		2		1			- относительная частота появления символа «Н»;
	16			8
p5		p6		p7						p8			1	- относительная частота появления символов «5», «6», «И»,
												16

Пробел.

При необходимости расчета логарифма по основанию два через логарифм по основанию десять можно воспользоваться соотношением:

lg x . log2 x lg 2

При использовании равномерного кода (например, СР-1251) длина кодовой комбинации определяется так:

nlog2 N ,

x- функция округления аргумента до ближайшего целого значения, не

меньшего, чем x .

В данном примере n log2 8 3бита.

Избыточность сообщения при кодировании равномерным кодом равна:

	L 1	2, 781	100% 7,3% .
		3

На первом этапе построения кода Шеннона-Фано формируется таблица абсолютных частот символов.

	Символ	Абсолютная час-	Символ	Абсолютная час-
		тота i		тота i
	7	4	5	1
	2	3	6	1
	3	3	И	1
	Н	2	Пробел	1

Для получения кодовых комбинаций строится кодовое дерево. При построении кода Шеннона-Фано дерево строится от корня к листьям (в отличие от настоящего дерева здесь корень располагается вверху, а листья – внизу). В качестве корня используется множество всех символов алфавита сообщения (рис. 1), упорядоченное по частоте встречаемости символов. Число сверху таблицы равно суммарной частоте символов в исходном сообщении.

Рис. 1 - Корень кодового дерева Шеннона-Фано

Затем множество символов делят на два подмножества так, чтобы новые множества имели равные, насколько это возможно, суммарные частоты встре-

12

_______________________________________________________________________________

чаемости входящих в них символов. Эти подмножества соединяются с корнем дерева ветвями, становясь потомками. Левая ветвь дерева обозначается символом 1, а правая ветвь – символом 0 (рис. 2).

Рис. 2 - Деление на подмножества

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

Кодовые комбинации (на рис. 3 они указаны в кавычках под соответствующими листьями) получаются при движении от корня дерева к кодируемому символу-листу путем сбора бит, присвоенных пройденным ветвям дерева. Запись кодовой комбинации ведут в направлении от старших разрядов к младшим. Например, при кодировании символа «3» сначала следует пройти по правой ветви к множеству {3, Н, 5, 6, И, Пробел} (к кодовой комбинации добавляется бит 0). Затем нужно пройти по левой ветви к множеству {3, Н} (к кодовой комбинации добавляется бит 1). Наконец, нужно пройти по левой ветви, чтобы достичь листа «3». Таким образом, получена кодовая комбинация «011».

Рис. 3. Дерево кода Шеннона-Фано

При декодировании биты считываются из входного потока и используются, как указатели направления движения по кодовому дереву от корня к искомому листу. При достижении листа найденный символ записывается в выходной поток, а движение по кодовому дереву снова начинают от корня. Например, декодирование комбинации «010» происходит следующим образом. Из потока считывается бит 0, следовательно, нужно пройти по правой ветви от корня дерева к узлу {3, Н, 5, 6, И, Пробел}. Следующий бит единичный, что требует пройти по левой ветви к множеству {3, Н}. Наконец, следующий бит 0 приводит декодер по правой ветви к листу «Н».

13

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

_______________________________________________________________________________

В следующей таблице приведены все разрешенные комбинации полученного кода Шеннона-Фано.

	Символ	Кодовая комби-	Символ	Кодовая комби-
		нация		нация
	7	11	5	0011
	2	10	6	0010
	3	011	И	0001
	Н	010	Пробел	0000

Закодированное сообщение будет иметь вид:

000101001000000010011110111010110011111001111

Общая длина закодированного сообщения составляет 45 бит.

Средняя длина кодовой комбинации равна (напомним, что число символов в сообщении – 16):

n45 2,813 бит/символ.

16

Избыточность сообщения после применения кода Шеннона-Фано снизилась до значения:

	L 1	2, 781	100% 1,13% .
		2,813

Несложно убедиться, что применение кода Шеннона-Фано позволило существенно уменьшить избыточность сообщения. При равномерном кодировании рассмотренного сообщения с помощью кодовой таблицы CP-1251 пришлось бы передать 128 бит.

4.3. Методические указания к заданию 3.3

В 1952 году Дэвид Хаффман предложил метод экономного префиксного кодирования с минимальной избыточностью. Как и код Шеннона-Фано, код Хаффмана требует получения априорных сведений о статистических свойствах источника сообщения, то есть необходима таблица абсолютных частот символов данного сообщения. На основе этих данных строится кодовое дерево, также называемое деревом Хаффмана или H-деревом. В отличие от кода ШеннонаФано, дерево Хаффмана строится в направлении от листьев к корню (в обратном направлении).

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

14

_______________________________________________________________________________

дальнейших построениях дерева. Процедура объединения свободных узлов ведется до тех пор, пока не останется единственный узел (корень дерева).

На рис. 4 показан первый этап построения дерева.

Рис. 4 - Первый этап формирования дерева Хаффмана

На втором шаге аналогично объединим общим родителем узлы, соответствующие символам «5» и «6». На третьем шаге, имея несколько возможностей для объединения узлов, выберем сформированные на первых двух шагах узлы с весом 2 (рис. 5).

Рис. 5 - Третий шаг построения дерева Хаффмана

На четвертом шаге объединяем узлы «3» и «Н», получая новый узел с весом 5 (рис. 6).

Рис. 6 – Четвертый шаг построения дерева Хаффмана

На пятом шаге узлами с наименьшими весами, используемыми для построения, выберем «2» с весом 3 и составной узел «5, 6, И, Пробел» с весом 4 (рис. 7).

Рис. 7 – Пятый шаг построения дерева Хаффмана

15

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

_______________________________________________________________________________

На шестом шаге объединяем узел «7» с весом 4 и составной узел «3, Н» с весом 5 (рис. 8).

Рис. 8 – Шестой шаг построения дерева Хаффмана

В результате объединения двух составных узлов «7, 3, Н» с весом 9 и «2, 5, 6, И, Пробел» с весом 7 получаем итоговое дерево (рис. 9).

Рис. 9 - Дерево Хаффмана

Кодовые слова формируются так же, как и в случае кода Шеннона-Фано. Все разрешенные кодовые комбинации кода Хаффмана приведены в таблице.

	Символ	Кодовая ком-	Символ	Кодовая комби-
		бинация		нация
	7	11	5	0011
	2	01	6	0010
	3	101	И	0001
	Н	100		0000

Закодированное сообщение выглядит так: «000110010000000010101111010101110011110110111». Общая длина закодиро-

ванного сообщения равна 45 бит, средняя длина кодовой комбинации

n45 2,813 бит/символ. Избыточность сжатого сообщения равна:

16

16

_______________________________________________________________________________

	L 1	2, 781	100% 1,13% .
		2,813

Средняя длина и избыточность для рассмотренного примера получились такими же, как у кода Шеннона-Фано.

Полученные коды Шеннона-Фано и Хаффмана обладают свойством префиксности. Это означает, что ни одна кодовая комбинация не является началом другой, что позволяет обеспечить однозначное декодирование и нет необходимости двоичные символы разделять пробелами.

Как уже отмечалось ранее, для кодирования и декодирования сообщений, сжатых по методам Шеннона-Фано и Хаффмана, кодек должен обладать априорной информацией о статистике сообщения. Поэтому кроме самого сообщения на приемную сторону необходимо передать таблицу частот символов данного сообщения, что увеличивает длину передаваемых данных и снижает фактическую эффективность сжатия. Тем не менее, этот недостаток нивелируется при сжатии больших объемов данных, например, при сохранении изображений в формате JPEG.

Список литературы

1.Алексеев А.П. Информатика 2007.– СОЛОН-ПРЕСС, 2007. – 608 с.

2.Shannon C. E. «A mathematical theory of communication», Bell Sys. Tech.

Jour., vol. 27, pp. 379-423; July, 1948.

3.Huffman D. A., «A method for the construction of minimum-redundancy codes», Proc. Inst. Radio Engineers, vol. 40, no. 9, pp. 1098-1101, Sep. 1952.

17

_______________________________________________________________________________

Приложение 1

Таблица СР-1251

пробел	32	!	33	"	34	#	35	$	36
%	37	&	38	'	39	(	40	)	41
*	42	+	43	,	44	-	45	.	46
/	47	0	48	1	49	2	50	3	51
4	52	5	53	6	54	7	55	8	56
9	57	:	58	;	59	<	60	=	61
>	62	?	63	@	64	A	65	B	66
C	67	D	68	E	69	F	70	G	71
H	72	I	73	J	74	K	75	L	76
M	77	N	78	O	79	P	80	Q	81
R	82	S	83	T	84	U	85	V	86
W	87	X	88	Y	89	Z	90	[	91
\	92	]	93	^	94	_	95	`	96
a	97	b	98	c	99	d	100	e	101
f	102	g	103	h	104	i	105	j	106
k	107	l	108	m	109	n	110	o	111
p	112	q	113	r	114	s	115	t	116
u	117	v	118	w	119	x	120	y	121
z	122	А	192	Б	193	В	194	Г	195
Д	196	Е	197	Ж	198	З	199	И	200
Й	201	К	202	Л	203	М	204	Н	205
О	206	П	207	Р	208	С	209	Т	210
У	211	Ф	212	Х	213	Ц	214	Ч	215
Ш	216	Щ	217	Ъ	218	Ы	219	Ь	220
Э	221	Ю	222	Я	223	а	224	б	225
в	226	г	227	д	228	е	229	ж	230
з	231	и	232	й	233	к	234	л	235
м	236	н	237	о	238	п	239	р	240
с	241	т	242	у	243	ф	244	х	245
ц	246	ч	247	ш	248	щ	249	ъ	250
ы	251	ь	252	э	253	ю	254	я	255

18