132
Кодты синтездеу процедурасы үш негізгі кезеңнен тұрады. Бірінші кезеңде кесте
жолдары бүктеледі: ең кіші ықтималдығы бар символдарға сәйкес екі жол жиынтық
ықтималдығы бар бір жолға ауыстырылады, осыдан кейін кесте қайта реттеледі. Үйірткі,
кестеде жиынтық ықтималдығы бірге тең, бір жол ғана қалғанша жүргізіледі (сурет 14.3,
б).
Сурет 14.3. Хаффман кодтаудың бірінші кезеңі
Екінші кезеңде бүктеулі кесте бойынша кодты ағашты құру жүзеге асырылады
(сур. 14.4, а). Ағаш кестенің соңғы бағаннан бастап салынады.
Ағаш түбірін соңғы бағанда орналасқан бірлік құрайды. Қарастырылған мысалда
бұл бірлік ағаштың екі торап түрінде көрсетілген 0,55 және 0,45 ықтималдықтан
жасалынады. Олардың біріншісі S
3
символға сәйкес, және осы тораптың онан әрі
бұтақтануы болмайды.
Екінші 0,45 ықтималдықпен белгіленген торап, үшінші деңгейдің ықтималдықтары
0,25 және 0,2 екі торабымен қосылады. 0,2 ықтималдық S
1
символға сәйкес, ал 0,25
ықтималдығы S
2
символдың пайда болуының ықтималдығынан 0,15 және S
4
символдың
пайда болуының ықтималдығынан 0,1 құрылады.
Сурет 14.4. Хаффман кодтаудың екінші кезеңі
Кодты ағаштың жеке тораптарын қосатын қабырғалар 0 және 1 цифрымен
нөмірленеді (мысалы, сол жақ қабырғалар – 0, ал оң жақтылары - 1).
Үшінші, соңғы кезеңде, кесте құрылады, онда көз символдары және оларға сәйкес
Хаффман кодының кодты сөздері салғастырылады. Осы кодты сөздер қабырғаларды
белгілейтін цифрларды оқудан пайда болады, қабырғалар ағаш түбірінен сәйкес символға
жолды құрайды. Қарастырылған мысал үшін Хаффман коды оң жақ кестеде көрсетілген
түрге келеді (сур. 14.4, б).
133
Бірақ классикалық Хаффман алгоритмның бір маңызды кемшіліг бар. Сығылған
хабар мазмұнын қалпына келтіру үшін кодтаушы пайдаланған жиілік кестесін декодер
білу керек. Демек, сығылған хабардың ұзындығы жиілік кестенін ұзындығына өсу керек.
Ол деректер алдында жіберілу қажет, сондықтан хабарды сығуға жұмсалған күштер босқа
кету мүмкін.
Статикалық Хаффман кодтаудың басқа варианты - кіру ағынды қарап шығу және
жиналған статистика негізінде кодтауды құрастыру. Мұнда файл бойынша екі өту қажет
болады – біреуі статистикалық ақпаратты қарау және жинау үшін, екіншісі – кодтау үшін.
Статикалық Хаффман кодтауда кіру символдарға (түрлі ұзындығы бар бит тізбектері)
айнымалы ұзындығы бар бит тізбектері сәйкестікке қойылады (олардың коды). Әрбір
символдың код ұзындығы оның жиілігінің теріс таңбалы екілік логарифмына
пропорционал алынады. Ал барлық кездескен түрлі символдардың ортақ жиынтығы ағын
алфавиті болып табылады.
Басқа да әдіс бар – адаптивті немесе динамикалық Хаффман кодтауы. Оның жалпы
принципі – кіру ағынның өзгерісіне байланысты кодтау схеманы өзгерту. Осындай жолда
бір өтімді алгоритм алынады және пайдаланған кодтау туралы ақпаратты айқын түрде
сақтауды қажет етпейді. Адаптивті кодтау статикалыққа қарағанда үлкен сығу дәрежесін
береді, өйткені кіру ағын жиілігінің өзгерістері толығырақ еске алынады.
Хаффман әдістері жеткілікті жоғары жылдамдық және сығудың орташа жақсы
сапасын береді. Бірақ Хаффман кодтауында минимал артықтық болады, егер әрбір символ
екі биттен {0, 1} тұратын жеке тізбекпен кодталатын болса. Осы әдістің негізгі кемшілігі -
сығу дәрежесінің символдар ықтималдықтарының 2-нің кейбір теріс дәрежесіне
жақындығына тәуелділігі, өйткені әрбір символ бүтін бит санымен кодталады.
Әбден басқа шешімді арифметикалық кодтау ұсынады. Бұл әдіс кіру ағынды
қалқыма нүктесі бар бір санға түрлендіруге негізделген. Арифметикалық кодтау кіру
алфавиттің символдарын шығынсыз буып-түюге мүмкіндік береді, егер осы
символдардың жиілік үлестіруі белгілі болса.
Арифметикалық кодтау әдісі арқылы сығуда қажетті символдар тізбегі кейбір [0, 1)
аралығындағы екілік бөлшек ретінде қарастырылады. Сығу нәтижесі осы бөлшек жазудың
екілік цифрлар тізбегімен ұсынылады. Әдіс идеясы келесі: бастапқы мәтін осы бөлшектің
жазуы болып қарастырылады, мұнда әрбір кіру символ шығу ықтималдығына
пропорционал салмағы бар «цифр» болып табылады. Осымен ағында символ шығуының
минимал және максимал ықтималдығына сәйкес интервал түсіндіріледі.
Қарастырылған әдістер деректердің қайтымды сығуын қамтамасыз етеді.
Тәжірибеде олардың программалық пен аппараттық іске асыруы қолданылады. Сығу
коэффициенті сығылатын ақпарат типіне байланысты 20-40% болу мүмкін.
Сонымен, криптографиялық шифрлау, бөгеуілге тұрақты кодтау және сығу бір
бірін аздап толықтырады, олардың комплекстік қолдануы берілетін ақпаратты сенімді
қорғау үшін байланыс арналарды тиімді пайдалануына көмектеседі.
Негізгі терминдер
Артықтық - қәдімгі бөгеуілге тұрақты емес кодпен салыстырғанда, кодты сөздің
ұзыңдығы қаншаға үлкейгенің көрсететін бөгеуілге тұрақты кодтың сипаттамасы. Көп
бөгеуілге тұрақты кодтар үшін артықтықты бақылау разрядтар санның кодты сөздің
жалпы разряд санына қатынасы ретінде анықтауға болады.
Код – белгілер жиынтығы және ақпаратты осы белгілер жинағы түрінде ұсынатын
ережелер жүйесі.
Кодты сөз – пайдаланатын ережелер жүйесіне сәйкес мүмкін болатын белгілердің
кез келген қатары.
Минимал кодтық ара қашықтық – кодты құрайтын кез келген қос түрлі кодты
сөздер үшін ең кіші Хэмминг бойынша қашықтық.
Достарыңызбен бөлісу: |
