Зертханалық жұмыс № 4

Хаффман бойынша кодтау принциптері

Жұмыстың мақсаты: Ақпаратты тиімді кодтау әдістерін зерттеу.

Хаффман бойынша кодтау әдістері және принциптерімен таныстыру және олардың практикада қолданылуы.

Мәліметтерді қысу екі этаптан тұрады. Бірінші этапта қысуға душар болатын мәліметтер есептеліп саналады; ал екіншіде 0-ден 255-ке дейінгі мәндерді қабылдай алатын мәліметтерде кездесетін жеке байттардың жиілігі анықталады.

Мысал қарастырайық. Сөз тізбегін қысу керек болсын:

ПРОГРАММИРОВАНИЕ КОМПРЕССИИ БЕЗ ПОТЕРЬ

Мәліметтерді қысқанға дейін әрбір әріп 0 және 255 сандарының арасында жататын сандармен көрсетіледі. Егер аты аталатын альтернативті кодтық кесте қолданылатын болса (құрамында орыс алфавитінің белгілері бар), онда әріптер 128 және 159 (а-я) арасындағы, 160 және 175 (а-п) арасындағы, 224 және 239 (Р-я) арасындағы мәндерге ие, ал пробел – 32 мәніне тиісті. Келтірілген сөз тізбегін жазуға әрбір әріпке бір байттан немесе пробелден келетін 38 байт қажет болатын еді. Жазылу кезіндегі файлдың мөлшерін төмендету үшін алдымен жеке әріптерде кездесетін жиілігін анықтаймыз.

Әріп | Жиілік
П | 3
Р | 5
О | 4
Г | 1
А | 2
М | 3
И | 4
В | 1
Н | 1
Е | 4
К | 1
С | 2
Б | 1
З | 1
T | 1
Ь | 1
Пробел | 3
№ р/р | Символ | Қайталау | Жиілік
1 | Р | 5 | 0.132
2 | О | 4 | 0.105
3 | И | 4 | 0.105
4 | Е | 4 | 0.105
5 | П | 3 | 0.079
6 | М | 3 | 0.079
7 | ПРОБЕЛ | 3 | 0.079
8 | А | 2 | 0.0526
9 | С | 2 | 0.0526
10 | Г | 1 | 0.0263
11 | В | 1 | 0.0263
12 | К | 1 | 0.0263
13 | Б | 1 | 0.0263
14 | З | 1 | 0.0263
15 | Т | 1 | 0.0263
16 | Ь | 1 | 0.0263
17 | Н | 1 | 0.0263

Сірә, көбіне Р әріпі жиі кездеседі. Басқа әріптер сирек кездеседі, ал көптеген әріптер мүлде кездеспейді. Әрине, әрбір әріптің бірдей бит санын кодтау амалына көп уақыт кетеді. Жиі кездесетін әріптерді қысқа кодтармен кодтау үнемдірек болар еді, мысалы, 0 немесе 1. Сонда кодтағанда барлығы бір бит қана жұмсалған болар еді, ол дегеніміз келісіліп жасалған кодтық кестеден 8 рет аз деген сөз. Сәйкесінше, әріптердің жиілігін төмендету шамасында оларды кодтау үшін барлық аса ұзын сандық мәндерді пайдалануға болар еді. Хаффман бойынша кодтау принциптері осындай болып табылады.

Белгілерінде кездесетін жиілікті анықтағаннан кейін кодтау тізбегі құрастырылады, көбінесе жиі кездесетін символдар кіші санды битпен кодталады, ал керісінше символдарда аз кездесетін жиілік үлкен санды битпен кодталады. Бұндағы есеп тиімді кодтау тізбегін / декодтау табу болып табылады. Қысылған файлдарға биттер потогын және бұл потоктың ақпаратты қалай интерпретациялауын жазып қою қажет. Бұл потоктағы биттердің жеке белгілері фиксерленбеген түрде емес ауыспалы сандар биті түрінде көрсетіледі, еске сала кететін жағдай кодталған биттер саны символдарда кездесетін жиіліктің өсуімен кішірейтіледі.

Кодтау алгоритмінің жүзеге асырылуы туралы мысалды қарастырайық.

Қайталанатын символдардың санын хабарлама ұзындығына бөлу арқылы қайталанатын символдардың жиілік кестесін құрастырайық (38):

Ең аз жиілігі бар жолдарды қосу және оны азайту бойынша сорттау арқылы жаңартылып алынған тізбектелген әуелгі кестедегі қатарды аламыз.

1 қадам
1 | 0.132
2 | 0.105
3 | 0.105
4 | 0.105
5 | 0.079
6 | 0.079
7 | 0.079
8 | 0.0526
9 | 0.0526
10,11 | 0.0526
12,13 | 0.0526
14,15 | 0.0526
16,17 | 0.0526
2 қадам
1 | 0.132
2 | 0.105
3 | 0.105
4 | 0.105
8,9 | 0.105
10,11,12,13 | 0.105
14,15,16,17 | 0.105
5 | 0.079
6 | 0.079
7 | 0.079
3 қадам
6,7 | 0.158
1 | 0.132
2 | 0.105
3 | 0.105
4 | 0.105
8,9 | 0.105
10,11,12,13 | 0.105
14,15,16,17 | 0.105
5 | 0.079
4 қадам
5,14,15,16,17 | 0.184
6,7 | 0.158
1 | 0.132
2 | 0.105
3 | 0.105
4 | 0.105
8,9 | 0.105
10,11,12,13 | 0.105
5 қадам
8,9,10,11,12,13 | 0.210
3,4 | 0.210
5,14,15,16,17 | 0.184
6,7 | 0.158
1 | 0.132
2 | 0.105
6 қадам
1,2 | 0.237
8,9,10,11,12,13 | 0.210
3,4 | 0.210
5,14,15,16,17 | 0.184
6,7 | 0.158
7 қадам
5,6,7,14,15,16,17 | 0.342
1,2 | 0.237
8,9,10,11,12,13 | 0.210
3,4 | 0.210
8 қадам
3,4,8,9,10,11,12,13 | 0.420
5,6,7,14,15,16,17 | 0.342
1,2 | 0.237
9 қадам
1,2,5,6,7,14,15,16,17 | 0.579
3,4,8,9,10,11,12,13 | 0.420

Енді, кері тізбектелген кестені падалана отырып, кодтау ағашын құрастырамыз. Мәліметтегі символдар тобының хабарламасындағы ықтималдық мәніне сәйкес келетін биіктіктен екі тармақ басталады.

Тармақтар 0 (сол жағы, ықтималдық қосындының кіші) және 1 (оң жағы, үлкен) мәндерімен белгіленеді. Ағаш әрбір символдың алфавит хабарламасымен аяқталады, ал мәні биіктігінен берілген символдарға дейінгі жолындағы ағаштың кірістірілген тармақтарының берілген символдарының екілік кодымен пайда болады.

Берілген операциялардың нәтижесі бойынша кодтау кестесін құрастыруға болады.

№ р/р | Символ | Екілік код
1 | Р | 101
2 | О | 100
3 | И | 010
4 | Е | 011
5 | П | 1110
6 | М | 1100
7 | ПРОБЕЛ | 1101
8 | А | 0010
9 | С | 0011
10 | Г | 00000
11 | В | 00001
12 | К | 00010
13 | Б | 00011
14 | З | 111100
15 | Т | 111101
16 | Ь | 111110
17 | Н | 111111

Ұзындықтың кодын символдың қосындысына көбейте отырып берілген ұзындықтың кодымен кодталып алынған қысу дәрежесін есептейміз.

3(5+4+4+4) + 4(3+3+3+2+2) +5(1+1+1+1) + 6(1+1+1+1) = 147 бит (18.4 байт)

Олай болса, қысу коэффициенті мынадай болады К=38/19=2

Хабарламаның декодтауын тексереміз. Мысалы, БАҒДАРЛАМА сөзі кодталсын:

1110101100000001010010110011000010

Қарауды декодттаған кезінде сол жағынан шығуға мүмкіндігінше 3 – биттік комбинациясы басталады, содан кейін 4-, 5- және 6-. Біздің жағдайда, кодтық кестеде 111 комбинациясы жоқ, ал 4 – биттік тізімде П әріпімен декодталатын 1110 комбинациясы бар. Хабарламада келесі биттерді қарау аналогиялық түрде жүргізіледі.

Бұл қысу схемасындағы қолданылатын шегі бізге белгілі: егер мәліметтердің жеке элементтері өзінде кездесетін жиілігімен ерекшеленсе, онда мәліметтерді қысуға болады. Егер мәліметтердің элементтері статистикалық тең бөлінсе, онда сығу мүмкін емес.

Растрлық графикте қолданылуы: егер көріністе тең боялған аймақтар бар болса, онда нәтижесі мәнді болады.

##### Өздік жұмыстарына арналған тапсырмалардың түрлері

1. Хаффман алгоритмі бойынша жолды өзіннің атынмен, әкеннің атымен, фамилиянды, туған айы мен күнінді кодтандар (мысалы, «Иванова Наталья Николаевна, 1 қаңтар 1990 жылы, «Тверь» қаласы).

2. Кодтаған кезінде жиелікті үтірден кейін төрт таңбасына (знака) кем дөңгелектемеңдер – нақтылық (точность) қысқаша кодтау тиімділігі төмендейді.

3. Қысу коэффициентін есептеңдер.

4. Осы жолды «Блокнот» редакторында теріңдер және мәтінді txt-форматында сақтаңдар ( файлдағы байттар санындағы таңбалар саны - әріпке, цифр және қызметтік (служебных) символдары жолға нақты (точности) сәйкес келуі керек).

5. Файлға кез келген архиваторды қолданыңдар және оны Хаффман алгоритмінің қысу дәрежесімен салыстырыңдар.

Бақылау сұрақтары:

1. Хаффман арқылы тиімді кодтаудың құру алгоритмін көрсетіңіздер.

2. Шеннон-Фано кодының Хаффман кодтарынан айырмашылығын көрсетіңіздер?

## ӘДЕБИЕТ

1. Цымбал В.П. Задачник по теории информации и кодированию. – М.: Высшая школа, 1994. – 276 с.

2. Шаврин Ю.А. Информационные технологии: Учебное пособие: В 2 тт: Т.1: Основы информатики и информационных технологии// Т.2: Офисная технология и информационные системы. Серия: Информатика. – М.: 2001.