Алексей Жоров гр. 14-502 Обязательное задание к практической работе №1 «Алгоритмы сжатия двоичной информации»

Алексей Жоров

гр. 14-502

Обязательное задание к практической работе №1

«Алгоритмы сжатия двоичной информации»

Статический алгоритм Хаффмана

Исходная информационная последовательность: 13 10 9 8 7 8 8 10 9 8 7 9 9 8 7 10 9 5

Символ	Статистика появления	Двоичное представление
13	1	0001
10	3	0010
9	5	0011
8	5	0100
7	3	0101
5	1	0110

Объем исходного текста: 18 (символов) х 4 (бита) = 72 бита

Символ	Частость	Код
13	1	0000
5	1	0001
10	3	001
9	3	10
8	5	11
7	5	01

Объем сжатого текста: 1х4 + 1х4 + 3х3 + 5х2 + 5х2 +3х2 =43 бита

К_сж = 43/72 = 1,67

Алгоритм Лемпеля-Зива LZ77

Сжатие

Словарь 16 бит																Буфер 7 бит							Код	Двоичный код
																13	10	9	8	7	8	8	0, 0, ’13’	0000 000 0001
															13	10	9	8	7	8	8	10	0, 0, ’10’	0000 000 0010
														13	10	9	8	7	8	8	10	9	0, 0, ‘9’	0000 000 0011
													13	10	9	8	7	8	8	10	9	8	0, 0, ‘8’	0000 000 0100
												13	10	9	8	7	8	8	10	9	8	7	0, 0, ‘7’	0000 000 0101
											13	10	9	8	7	8	8	10	9	8	7	9	3, 1, ‘8’	0011 001 0100
									13	10	9	8	7	8	8	10	9	8	7	9	9	8	1, 4, ‘9’	0100 100 0011
				13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5		2, 3, '10’	0010 011 0010
13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5						2, 1, ‘5’	0010 001 0110
9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5

Распаковка

Двоичный код	Код для распаковки	Словарь 16 бит																Восстановленный текст
0000 000 0001	0, 0, ’13’																13	13
0000 000 0010	0, 0, ’10’															13	10	10
0000 000 0011	0, 0, ‘9’														13	10	9	9
0000 000 0100	0, 0, ‘8’													13	10	9	8	8
0000 000 0101	0, 0, ‘7’												13	10	9	8	7	7
0011 010 0100	3, 1, ‘8’										13	10	9	8	7	8	8	8 8
0010 100 0011	1, 4, ‘9’					13	10	9	8	7	8	8	10	9	8	7	9	10 9 8 7 9
0010 011 0010	2, 3, '10’	13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9 8 7 10
0010 001 0110	2, 1, ‘5’	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5	9 5

Объем исходного текста: 18 (символов) х 4 (бита) = 72 бита

Объем сжатого текста: 9 (кодов) х 11 (бит)= 99 бит

К_сж= 99/ 72 = 1,38

Алгоритм Лемпеля - Зива - Сторера - Шимански LZSS
Сжатие

Словарь 16 бит																Буфер 7 бит							Код	Двоичный код
																13	10	9	8	7	8	8	0, ’13’	0 0001
															13	10	9	8	7	8	8	10	0, ’10’	0 0010
														13	10	9	8	7	8	8	10	9	0, ‘9’	0 0011
													13	10	9	8	7	8	8	10	9	8	0, ‘8’	0 0100
												13	10	9	8	7	8	8	10	9	8	7	0, ‘7’	0 0101
											13	10	9	8	7	8	8	10	9	8	7	9	0, ‘8’	0 0100
										13	10	9	8	7	8	8	10	9	8	7	9	9	0, ‘8’	0 0100
									13	10	9	8	7	8	8	10	9	8	7	9	9	8	1, 1, 4	1 0001 100
					13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5	0, ‘9’	0 0011
				13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5		1, 2, 3	1 0010 011
	13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5					1, 1, 2	1 0001 010
10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5							0, ‘5’	0 0110
9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5

Распаковка

Двоичный код	Код для распаковки	Словарь 16 бит																Восстановленный текст
0 0001	0, ’13’																13	13
0 0010	0, ’10’															13	10	10
0 0011	0, ‘9’														13	10	9	9
0 0100	0, ‘8’													13	10	9	8	8
0 0101	0, ‘7’												13	10	9	8	7	7
0 0100	0, ‘8’											13	10	9	8	7	8	8
0 0100	0, ‘8’										13	10	9	8	7	8	8	8
1 0001 100	1, 1, 4						13	10	9	8	7	8	8	10	9	8	7	10 9 8 7
0 0011	0, ‘9’					13	10	9	8	7	8	8	10	9	8	7	9	9
1 0010 011	1, 2, 3		13	10	9	8	7	8	8	10	9	8	7	9	9	8	7	9 8 7
1 0001 010	1, 1, 2	10	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	10 9
0 0110	0, ‘5’	9	8	7	8	8	10	9	8	7	9	9	8	7	10	9	5	5

Объем исходного текста: 18 (символов) х 4 бита = 72 бита

Объем сжатого текста: 9 (кодов) х 5 бит + 3 (кодов) х 8 бит = 69 бит

К_сж= 69/ 72 = 0,96