Лекция 7 Деңгей бойынша кванттау

Тиімді, бір өткізгішті, код кестесін жіберуді талап етпейді.Оның негізі адаптивті алгоритмді қолдану болып табылады, яғни алгоритм әрбір символға кодты сәйкестендіргенде есептеудің ішкі жүрісін келесі кезекте осы символға басқа код сәйкес келетіндей етіп өзгертеді, яғни кодтауға келіп түсетін символға алагритмнің қалыптасуы болады. Ал декодтағанда да осындай процесс жүреді.

Алгоритм жұмысының басында кодтау ағашында әрқашанда 0 жиілігіне ие, бір аранайы символ болады.Ол ағашқа жаңа символ енгізу үшін қажетті:одан кейін символ коды міндетті түрде жіберіліп отырады. Көбінесе осындай символдарды escape – символы деп атайды. Кеңейтілген ASCII әрбір символды 8 биттік санмен, яғни 0-ден 255-ке дейін, кодтайды.кодтау ағашын құрастырғанда дұрыс декодтау мүмкіндігі болу үшін ағаш құрылымын ретке келтіруі керек. Ағаш жапырақтарын жиіліктің өсу ретімен және содан кейін символдардың стандартты кодтарының өсу ретімен орналастырамыз. Түйіндер солдан оңға қарай үздіксіз жинақталады. Сол жақатағы бұтақтар-0, ал оң жақтағы- 1 санымен белгіленеді.

Адаптивті емес Хаффмен кодын құрастыруға арналған 2 мысалдағы Х дискретті кездейсоқ шама 10-дық мәнін таңдауға сәйкес келетін АССВСАААВС мәліметі үшін Хаффменнің адаптивті алгоритм арқылыкодты құрастыру процессін қарастырайық :

Енді ‘A’0’C’100’B’1001010100101 мәліметін де кодтау процессін қарастырайық. Мұнда және одан кейін де апострофтағы символ- ASCII+ кестесіндегі екілік санның жазылудың символ нөмерін көрсететін 8 битті білдіреді.Декодтаудың басында Хаффмен ағашы 0 жиілігіндегі escape-символға ғана ие. Әрбір жаңа символдыкодтаған сайын, ағаш қайтадан құрылады.

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

Бинарлық ағашты реттелген деп атайды, егер олардың түйіндері саламғының көбеюі бойынша және осы ортақ басшылары бар түйіндер топтамасы бір-бірінің жанында, бір тізбекте орналасса.

4- суретте Хаффмен реттелген ағашына мысал келтірген.

5-сурет.
Егер кодтау ағашы реттелген болса, онда түйіндердің салмағы өзгерген кезден ағаштың барлығын қайтадан құрастыру қажет емес-онда тек қана екі түйіннің, яғни салмағы реттілікті бұзған түйін мен одан кейінгі салмағы төмен түйін, орнын ауыстыру керек. Түйіндер орны ауысқананн кейін, барлық түйіндер салмағын есептеу қажет.

Мысалы, 4-суреттегі ағашқа тағы да екі А әрпін қоссақ, онда алдымен А түйіні мен D және B түйіндері орындарын ауытыру қажет(5-сурет).

Егер тағы да екі А әрпін қоссақ, онда алдымен А түйіні мен D және B түйіндері үшін басшы түйінінің орындарын ауыстырып, содан кейін Е түйіні мен Е аға-түйінінің орнын ауытыру қажет(6-сурет).

6-сурет.