 |
Тақырып №13. Хаффман коды
|
|
|
|
Тақ ырып №13. Хаффман коды
Хаффман ә дісі айнымалы ұ зындық ты кодтардың алгоритмін қ ұ ру ү шін µте ың ғ айлы болып табылады. Егер символдардың ық тималдылығ ы 2 санының теріс дә режесіне тең болса, онда Хаффман ә дісі символдарды жақ сы сығ уғ а мү мкіндік береді. Хаффман алгоритмінің аѓашы тө меннен жоғ ары қ арай қ ұ рылады, содан кейін аѓаш бойынша тө мен тү седі. Ә рбір жеке код солдан оң ғ а қ арай қ ұ ралады(ең кіші биттен ү лкен битке қ арай).
Алгоритм, алфавит символдарының тізімін ық тималдық тары кему ретімен қ ұ рудан басталады. Содан кейін тү бінен бастап аѓаш қ ұ рылады. Аѓаштың б±тақ тары болып осы символдар қ ызмет етеді. Бұ л қ адам бойынша жасалады жә не ә рбір қ адамда ең аз ық тималдылығ ы бар екі символ алынады. Осы алынғ ан символдарды кө рсете алатын кө мекші символмен ауыстырылады. Кө мекші символғ а, осы символдар қ адамында таң далғ ан, ық тималдық тар қ осындысына тең ық тималдық тар меншіктеледі. Тізім бір ғ ана қ осымша символғ а дейін кішірейгенде аѓаш қ ұ ралғ ан деп есептелінеді. Алгоритм барлық символдардың кодтарын қ ұ румен аяқ талады.
Осы алгоритмді қ арапайым мысалда кө рсетейік.
Ық тималдығ ы а1= 0. 4, а2 =а3 =0. 2, а4= а5 =0. 1 символдар берілсін. Символдарды бір- бірімен келесі ретпен жұ птастырмыз:
1. 
символы 
символымен бірігіп, 
біріктірілген символмен ауыстырылады. Бұ л символдың ық тималдылығ ы 0, 2.
2. 0, 3 ық тималдылығ ы бар 
жә не 
, сонымен қ атар 0, 2 ық тималдылық тары бар 
жә не символдар қ алды. Еркін тү рде жә не символдарын таң даймыз. Оларды біріктіріп ық тималдылығ ы 0, 4 болатын 
қ осымша символымен ауыстырамыз.
|
|
|
3. Енді ық тималдылық тары 0, 3, 0, 3 жә не 0, 4 болатын , жә не символдары бар. жә не символдарын 0, 7 ық тималдылығ ы бар 
символына біріктіреміз.
4. Сонынада қ алғ ан жә не символдарын біріктіріп, ық тималдылығ ы 1 болатын 
символына ауыстырамыз.
Нә тижесінде, осығ ан сә йкес келетін ағ аш қ ұ растыруғ а болады Символдың кодтарын белгілеу ү шін біз еркін тү рде ә рбір жұ п ү шін жоғ арғ ы бұ тақ қ а 1 бит жә не тө менгі бұ тақ қ а 0 бит меншіктейміз. Нә тижесінде келесі кодты аламыз: 0, 10, 111, 1101 жә не 1100.
Негізгі ә дебиеттер: [1, 2, 3, 9]
Қ осымша ә дебиеттер: [11, 12]
Тақ ырып №14. Арифметикалық кодтау
Арифметикалық кодтауда, жеке символдарды кодтаудың орнына, барлық мә ліметке бір ѓана код береді. Енетін файл ретінде мә тін, бейне басқ а да мә ліметті алуғ а болады. Бұ л алгоритм енетін файлдың символдарын біртіндеп оқ иды жә не сығ ылғ ан файлғ а биттерді қ осады. Бұ л ә дісті тү сіну ү шін алынғ ан кодты [0, 1) интервалындағ ы сан ретінде қ арастыру керек(мұ ндағ ы [a, b) a жабық, b ашық ). М±нда «9746509» кодын «9. 9746509» коды ретінде тү сінеді, бірақ «0. » бө лігі жіберілген файлғ а қ осылмайды.
Бірінші қ адамда алфавиттегі ә рбір символдың пайда болу жилігін анық тау қ ажет. Ең жақ сы нә тижені енетін файлдың барлығ ын оқ у барысында ғ ана алуғ а болады.
Бірінші мысалда ық тималдық тары P1=0. 4, P2=0. 5 жә не P3=0. 1 болатын 
символдарын қ арастырамыз. [0, 1) интервалы осы ү ш символғ а қ атысты пропорционал бө ліктерге бө лінеді. Бұ л интервалдардың орналасу реті маң ызды емес. Қ арастырылып отырғ ан мысалда 3 символғ а [0, 0. 4), [0. 4, 0. 9) жә не [0. 9, 1) интервалдары сә йкес келеді. « 
» жолдарын кодтау ү шін біз [0, 1) интервалын бө луден бастаймыз. Бірінші символы бұ л интервалды басынан 40%, сонынан 10% қ ысқ артады. Нә тжесінде [0. 4, 0. 9) интервалын екінші символы [0. 6, 0. 85) аралық қ а дейін қ ысқ артады. Ү шінші символы [0. 7, 0. 825)- ге дейін мә нін ауыстырады. Ең сонында символы басынан 90% -ті алып тастайды, ал соң ғ ы нү ктені ө згеріссіз қ алдырады. Сонында [0. 8125, 0. 825) интервалы қ алады. Біздің нә тижелік код ретінде осы аралық тағ ы кез келген санды алуғ а болады. [0. 6, 0. 85) интервалы [0. 4, 0. 9) интервалынан келесі тү рлендіру бойынша алынады. 0. 4+(0. 9-0. 4)х0. 4=0. 6 жә не 0. 4+(0. 9-0. 4)х0. 9=0. 853
|
|
|
Осы мысал арқ ылы арифметикалық кодтау алгоритмнің келесі қ адамдарын атап айтуғ а болады:
1. [0, 1) ағ ымдық интервалды беру;
2. Ә рбір енетін S файлғ а келесі қ адамдарды қ айталаң ыз;
2. 1 Ағ ымдағ ы интервалды ә рбір символдың ық тималдығ ына байланысты пропорционал бө ліктерге бө лің із;
2. 2 S1символына қ атысты интервалы таң дап, оны ағ ымдағ ы интервал ретінде алу;
3. Енгізілген барлық файл ө ң делгеннен кейін, алгоритмнің шығ уы деп кез - келген нү кте алынады. Кез - келген ө ң делген символдан кейін, ағ ымдағ ы символ сығ ылып отырылады. Кодтың орташа ұ зындығ ы табу ‰шін шығ атын биттер ө лшемін енетін символдар ө лшеміне бө лу керек.
Негізгі ә дебиеттер: [1, 2, 3]
Қ осымша ә дебиеттер: [11, 12]
|
|
|
