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 Егер
схемасы префикс қасиетіне ие болса, онда алфавитті
кодалау өзара бір мәнді болады.
Жоғарыда қарастырылған мысалдан
көрінгендеі, префикстік қасиеті қажетті шарт емес:
префикстік қасиетіне ие болмаса да, алфавитті
кодалау өзара бір мәнді болады.