2 Лаборатория машғулоти Мавзу: Ахборот кодлашртиришниг самарали усулларини ўрганиш Машғулот мақсади

Мисол1: Қуйидаги кўринишда ахборот берилган: BBCBBBCDDEDAAADDFFGGHHEE. Ушбу ахборотда умумий белгилар сони 24 та. Дастлаб ушбу ахборот учун энтропия кўрсаткичини қийматини ҳисоблаймиз. Н(х) = ∑ Р(х) * Log ₂ Р(х) = 2,89 бит га тенг бўлади.
Ушбу алгоритм бўйича ҳисоблаш натижалари жадвал 2.1 келтирилган.
Шеннона Фано алгоритми бўйича ҳисоблаш натижалари.
Жадвал 2.1

Белгилар	Пайдо бўлиш частотаси	Ёрдамчи жадвал						Коди
B	5	5 (1) 5 (1) 3 (1)	5 (1)				11
D	5		5 (0) 3 (0)		5 (1)		101
A	3				3 (0)		100
E	3	3 (0) 2 (0) 2 (0) 2 (0) 2 (0)	3 (1)		3 (1)		011
C	2		2 (1)	2 (0)			010
F	2		2 (0) 2 (0) 2 (0)	2 (1)				001
G	2			2 (0) 2 (0)		2 (1)		0001
H	2					2 (0)		0000

Кодли комбинациянинг ўртача узунлигини ҳисоблаймиз:
n _урт = ∑ n _i * Р(х) = 2,96 битга тенг.

Ҳозирги кунда энг кенг тарқалган, амалиётда кўп ишлатиладиган энтропияли кодлаш усулига асосланган йўқотишсиз сиқиш алгоритмларидан бири бу –Хаффман алгоритми ҳисобланади. Хаффман алгоритми асосида матнли ахборотлар сиқилади.

1. 
   Ахборотдаги барча белгилар сони, яъни N ни ҳисобланади
   
2. 
   Жами N та белгидан иборат бўлган ахборотдаги ҳар бир белгининг пайдо бўлиш частотаси ҳисобланади.
   
3. 
   Ҳар бир белгининг пайдо бўлиш частотасини камайиб бориш тартибида жадвалга жойлаштирилади
   
4. 
   Жадвалдаги охирги иккита частота йигиндиси ҳисобланиб, битта умумий бўлган йиғинди частотага бирлаштирилади
   
5. 
   Ҳисобланган янги йиғинди частотадан ва ҳисоблашда қатнашмаган бошқа частоталардан жадвалнинг янги устуни ҳосил қилинади (бунда ҳам частоталар камайиб бориш тартибида жойлаштирилади)
   
6. 
   Шу тарзда то битта умумий N га тенг булган йигинди ҳосил бўлгунча жараён давом этаверади
   
7. 
   Жадвал тўлдирилгандан сўнг, жадвалдаги ҳисоблашларга мувофиқ дарахт қурилади.
   
8. 
   Дарахтнинг тепа қисмида N жойлашган бўлади ва уни тенг иккига бўлиш керак, ҳосил бўлган натижаларни яна тенг иккига бўлиш керак. Шу тарзда ахборотдаги ҳар бир белгини пайдо бўлиш частотаси топилгунча бўлишни давом эттириш керак.
   

Мисол 2: Қуйидаги кўринишда ахборот берилган: BBCBBBCDDEDAAADDFFGGHHEE.
Ушбу алгоритм бўйича ҳисоблаш натижалари жадвал 2.2 келтирилган.
Хаффмен алгоритми бўйича ҳисоблаш натижалари.
Жадвал 2.2.

Белгилар	Пайдо бўлиш частотаси	Ёрдамчи жадвал
B	5	5	5	6	8	10	14	24
D	5	5	5	5	6	8	10
A	3	4	4	5	5	6
E	3	3	4	4	5
C	2	3	3	4
F	2	2	3
G	2	2
H	2

белгилар	B	D	A	E	C	F	G	H
коди	01	00	100	101	1101	1100	1111	1110

Кодли комбинациянинг ўртача узунлигини ҳисоблаймиз:

n _урт = ∑ n _i * Р(х) = 2,92 битга тенг.
Мустақил ишлаш учун топшириқлар

Вариант	хабарлар
1	BBCCCCDEEEEFFFFGGGGFFFFFFDD
2	DFABBBEECEDDEFFFAEBBCBBBBBBC
3	CCCCCCCCCCCBBBBBAAAADDDDEEEF
4	BCDEEFAACCADEEDDDEDBAAEEEDDD
5	AAAAAAAABBAAAABBBCCCCCDDDDDEEE
6	CEDDBCEFABBBFDDFAEBAADDDEEAAA
7	BBCBBDBBDEEFDABBDABBBBACACCEG
8	DDFEBBCAADAEFFBEGHAABFFBD
9	BBCBBBCDDEDAAADDFFGGHHEE
10	DDECBFFEEEAAADBBBEEEAAAAABBB
11	CAADDDAEDADDEAAEBEFBEDEFEEA
12	FFFBBCDEEAAFDFFGBBGFADAABFFFF
13	CEEFFDDDEBBAAAEDEDAECBAADDD
14	EEEEBBBEEEEBBCCCCDDDDFFFFAEEEE
15	GBDBBBADDABADAAAFFFEEEEBBBEE
16	BBBAAAEDDAAABBFEFFDDEEGAAAAA
17	FFFBBCDEEAAFDFFGBBGFADAAA
18	GFFFFBBBBAAAACCFFFFFCCDDE
19	ABBCEHABCAEGAAAAAADADDDD
20	AAAAAAABBCCDDEEFFGGHHHAAAA
21	ABBBCEDDEFFFAEBBCCCCADAAABB
22	DDDDDDDDAAABBBCCCDDDEEEFFF