4.3 Кодтан шығарудың бірмәнділік критерийі

 

Мұнда біз  және  алфавиттер үшін келесі  схемамен  берілетін алфавитті кодалауды қарастырпмыз:

а1 – В1

а2 – В2

                                                            . . . . .                                                  (S)

 ar – Вr.

 

 болсын, яғни ақпараттар көзі  алфавиттегі барлық сөздерді жасайтын болсын. Алфавитті кодалау  жиынынын  жиынға бейнелеуін. Обозначим через  образ множества  в этом отображении. Жасайтыны айқын.

Бұл бейнелеудегі  жиынының бейнесін  арқылы белгілейміз.

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

Мысал.  және   алфавиттер арасындағы келесі схема бойынша берілген алфавитті кодалауды қарастырамыз:

а1 – b1

а2 – b1 b2.

 және  сәйкесінше  пен  кодтары болсын. Түсінікті, егер  болса, онда .

Кодтан шығаруы келесі түрде орындалады. В сөзді, , қарапайым кодтарға бөлеміз. b2 әріптің В сөзіне әрбір кіруі алдында b1 әріпі бар екендігін ескертіп өтейік. Бұл барлық (b1b2) қосақтарды ажыратуға мүмкіндік береді. В сөздің қалған бөлігі  b1 әріптерден тұрады. Енді әрбір (b1b2) қосақты – а2 әріпке, ал қалған b1 әріптердің әрбірін  –  а1 –ге ауыстыра отырып, В сөздің түпбейнесі болатын А сөзін аламыз.

В = b1 b1 b2 b1 b2 b1 b1 b1 b2 болсын. Қосақтарды ажыратқан соң қарапайым кодтарға келесі жиктеуді аламыз:

В = b1( b1 b2)( b1 b2) b1 b1( b1 b2),

демек,

А = а1 а2 а2 а1 а1 а2.

Алфавитті кодалау өзара бірмәнділік қасиетіне ие болмайтын көптеген мысалдарды келтіру мүмкін. Осыған байланысты мынадай сұрақ пайда болады: алфавитті кодалаудың  схемасы бойынша алфавитті кодалау өзара бірмәнділік қасиетіне ие ме әлде жоқ па екtнін бола ма?

Анықтама. В  сөзі  түрде болсын. Онда   сөзі – В сөздің басы немесе префиксі, ал  –В сөздің соңы деп аталады.  бос сөз және В сөздің өзі В сөздің басы мен соңы деп саналады. В сөзден өзгеше оның басы мен соңы өзіндік деп аталады.

Анықтама. Егер кез келген i және j() үшін Bi сөзі B j  сөздің префиксі болмаса, онда  схемасы префикс қасиетіне ие деп айтады.

 Теорема 1 Егер  схемасы префикс қасиетіне ие болса, онда алфавитті кодалау өзара бір мәнді болады.

Жоғарыда қарастырылған мысалдан көрінгендеі, префикстік қасиеті қажетті шарт емес:  префикстік қасиетіне ие болмаса да, алфавитті кодалау өзара бір мәнді болады.