лаба №3 / Лаба3

Цель работы: закрепление знаний по методам кодирования информации.

Задание: используя заданный текст определить: - Избыточность заданного текста, вызванную неравно вероятностью появления символов в сообщении; - Избыточность, вызванную статистической связью между соседними символами; - Полную избыточность. 2. Используя заданный текст построить оптимальный неравномерный код, применяя: - Метод Шеннона-Фано; - Метод Хаффмана. 3. Определить для каждого метода среднюю длину символа исходного алфавита, коэффициент статистического сжатия, коэффициент относительной эффективности 4. Закодировать исходный текст методом Шеннона-Фано и методом Хаффмана.

Ход работы

1. Используя заданный текст, определили избыточность заданного текста, вызванную неравно вероятностью появления символов в сообщении:

D_p=0,11228

Заданный текст

Проснувшись однажды утром после беспокойного сна, Грегор Замза обнаружил, что он у себя в постели превратился в страшное насекомое. Лежа на панцирнотвердой спине, он видел, стоило ему приподнять голову, свой коричневый, выпуклый, разделенный дугообразными чешуйками живот, на верхушке которого еле держалось готовое вот-вот окончательно сползти одеяло. Его многочисленные, убого тонкие по сравнению с остальным телом ножки беспомощно копошились у него перед глазами.

2. Используя заданный текст, построили оптимальный неравномерный код, применяя формулу:

а)Код Шеннона – Фано

Алфавит из n букв располагали в порядке убывания вероятностей их появления в сообщениях.

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

по возможности равны.

Первой группе присвоили символ 1, второй группе - символ 0.

Каждую из образованных подгрупп поделили на две части таким образом, чтобы суммарные вероятности вновь образованных подгрупп были по возможности равны.

Первым группам каждой из подгрупп вновь присвоили 1, а вторым - 0. Таким образом, получается второй символ кода. Затем каждая из полученных групп вновь поделили на равные части до тех пор, пока в каждой из подгрупп не останется по одной букве. Вставить код шеннона фано из паскаля.

Построили таблицу Шеннона – Фано

Таблица 1. Метод Шеннона – Фано

Символ	КОД
ю	001100010
щ	001100011
З	00110000
Л	001100110
П	001100111
Г	00110010
-	001101010
Е	001101011
ц	00110100
х	00110110
.	00110111
я	001110
ш	0011110
з	0011111
ч	001000
ж	001001
б	001010
ь	001011
й	000110
ы	000111
,	00010
д	00000
к	00001
г	01000
м	01001
у	01010
п	01011
в	01110
т	01111
р	0110
л	11110
с	11111
и	1110
а	1100
н	1101
е	100
о	101

б) Код Хаффмана

объединение частот:

- две последние частоты списка складываются, а соответствующие символы исключаются из списка;

- оставшийся после исключения символов список пополняется суммой частот и вновь упорядочивается;

- предыдущие шаги повторяются до тех пор, пока ни получится единица в результате суммирования и список ни уменьшится до одного символа.

Таблица 2. Метод Хаффмана

Символ	Количество	Вероятность, %		Код
	61	13.062%	100
о	61	13.062 %	11
е	35	7.494 %	1101
н	31	6.638 %	1011
а	21	4.496 %	10
и	21	4.496 %	1
с	21	4.496 %	0
л	19	4.068 %	11110
р	19	4.0685 %	11101
т	18	3.8543 %	11001
в	16	3.426 %	10101
п	14	2.9978 %	1011
у	12	2.5695 %	1010
м	11	2.3554 %	111111
г	11	2.3554 %	111
к	11	2.3554 %	110
д	10	2.1413 %	111110
,	9	1.9271 %	111000
ы	8	1.7130 %	110000
й	7	1.4989 %	101000
ь	6	1.28479 %	10011
б	6	1.28479 %	10001
ж	6	1.28479 %	10000
ч	5	1.0706 %	1110011
з	5	1.0706 %	1110010
ш	5	1.0706 %	1100011
я	4	0.85653 %	1100010
.	3	0.64239 %	100101
х	1	0.21413 %	101001111
ц	1	0.21413 %	101001110
Е	1	0.21413 %	101001101
-	1	0.21413 %	101001100
Г	1	0.21413 %	101001011
П	1	0.21413 %	101001010
Л	1	0.21413 %	101001001
З	1	0.21413 %	101001000
щ	1	0.21413 %	10010011
ю	1	0.21413 %	10010010
	1	0.21413 %	1001000

3. Определили для каждого метода среднюю длину символа исходного алфавита.

l_ср=176,98

Определили коэффициент статистического сжатия.

K_сс= 0,02850

Определили коэффициент относительной эффективности.

К_оэ=0,0253

4. Закодировали исходный текст методом Шеннона – Фано и методом Хаффмана.

Метод Шеннона – Фано:

0011001110110101111111101010100111000111101110111110010111010101000001101110000100100000000111101001010011110110101010011010010111011111111110100101000101010011111010111010000110100011011011010100010110101111111011100000101010001100100110100010001010110101000110000110001001001111111001010101001010110111000110010100010011110111100001010100010000111110110101011101101001010101011111100001010001110101001110101001011101111110111110011110111010100101101101000111001101100011111110111101111100111010100111010101111101111011011000011110110110110010101101110011111100000011010100110110000110111101000110011010000100111001010110111001010010111100110100110100111001101101101011110111010001100000010100011010101111101011111011011000001010101011101101001110111000000100111100001010101111101111101111011110101101010001001010101010010110110111001011101000001101001110011110010111010010001011111010101110010100001010101111101110101000110101000001101011011100010001101100011100001110001100001010100111000011101011010100000111110000111000110000101010011011000011111000001001111010011011101000111000110101000000010100100010110100101001101100001111111010001110100111101010001000100001111001010000110000011100010011110101000100111100111010101111000101010110111001010011101000110001101100101000111100000110010100000110101111101011010101000101101010011110100101000000100011000100111001111010111111001011101001000101011111010111010110010100111010101111001101010011101010111110101010000110111010010001100011111001111000101111011011010111110101110111110001111101111111010101010000010000111011110101001101111010001101011010001011010010011101101010001010010001110111111111010011011101000111100000101010010100010101010100010110100111110111010000111101001010010111011010111110110110001110110110011011110001100010101011111101010111111011111100111100010111101000111010011010011111001111010101001101011011010010010000111101010001010100111110101110101001101001100011110110110100000110101011101001111011101111011101111100101110100101010101101100010001011010010111000110100000001010010001111011000011111110001001111000110111

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

101001010111010110000101101010101011100011000100000100111000111111101011001001000011111011000010001010110011110101111111110001011011000011110110110001000111010000010110110011001110100010110110011101110000001011001011100010010100101111101110100111011111011001010010000010111111111001000101000110100011011001011101010100100000001111101110001001110011110010111000111011100010101000000110101000111000101001010110001011011000011001110111110000110001011111011101101011110100101100100011111000001100010100101011000000110011110100101100011101101111011001011001000001101001100111111110111101010010110010100100111010100000010100101100101000101100101011101001110000111101101101111001101011101111011111100111010001000000010110001101111011110001000111011100101010001111110110111110111000100000011001011000111110011100110111111101010100010111110100010101101111111010111100010110010100111000011101111110011101010101011100010000001010101110100010000110011111010001111001110111101101011100001010001110001001010111000001011010100011011110110000101000111000100111010010111001011111011011111011011011101111000010100010011111001010001110110110100011110100101110010101111000011111100011001110011110111000110101010100000110001011111100011000100000001101010111100111100010010110010100101011101111011010011110101011000110011011011000011001111001011111010110011101110011011111011011001111101101111010100000010111100110000010011100001110111100101110101011110110010101011110011010011001010101111001100011001100111011111001100101100111011111001001110110111000000010110111111011100101100100011000111111101101110001011110011010010110010100110100111011100111111101101100111011111001100010000111101101101110111100001101111000100010100100010110011101110011001011101100110000111011000101101110000001110100101010110111101101100010100100101000000100011000011001001011110010011101111000011111110011001110111110011111111100101101101000000110000110001000111010000010110111111110110100100111011011100001100110101101111000110001111100001000001001110001010100101111010011101110001011110111101110111111010000111111100010111001000101111110001010010101001000

Вывод: в ходе лабораторной работы закрепление знаний по методам кодирования информации.