4.3. 4.3. Keresési stratégiák és prefix kódok

Elképzelhető olyan keresési feladat, ahol egyszerre legfeljebb csoportról tudjuk egyetlen kísérletre eldönteni, hogy a keresett elem melyikben van.

Absztrakt megfogalmazás: Legyen a keresett dolog az véges halmaz valamelyik eleme. A -t valószínűségi változónak tekintjük: a eloszlása. A kesesési stratégiák definiálásához és áttekintéséhez felhasználjuk a gráfos leírásukat.

Fának nevezzük az olyan irányított gráfokat, melyek egy kitüntetett szögpontjából, a kezdőpontból, ágak (irányított utak) indulnak ki, melyek a későbbi szögpontokban ismét elágaznak, de újra biztosan nem találkozhatnak. Azokat a szögpontokat, melyekből további élek már nem indulnak ki, végpontoknak nevezzük. Mivel az ágak újra nem találkozhatnak, a kezdőpontot mindegyik végponttal pontosan egy ág köti össze. Az ágat alkotó élek számát az ág hosszának nevezzük.

Tekintsünk egy végpontú fát és rendeljük hozzá kölcsönösen egyértelmű módon a fa végpontjaihoz (ágaihoz) az elemű halmaz elemeit. Az ilyen módon cimkézett végpontú fát az halmaz kódfájának nevezzük. Ha a kódfa minden szögpontjához az halmaznak azt az részhalmazát rendeljük hozzá, amely a szögponton áthaladó ágak végpontjaihoz tartozó elemekből áll, akkor olyan megfeleltetést kapunk a szögpontok és az bizonyos részhalmazai között, hogy bármelyik szögponthoz rendelt halmaz a szögpontból kiinduló élek végpontjaihoz tartozó, páronként diszjunkt halmazok egyesítése. Látható, hogy az halmaz olyan kódfája, ahol minden szögpontból legfeljebb él indul ki egy alternatívás keresési stratégiát definiál. Ez a megfeleltetés kölcsönösen egyértelmű.

Ha akkor a megtaláláshoz szükséges lépések száma az végpontba vezető ág hossza. A feladat az

várható lépésszám minimalizálása. Mivel egy lépéssel legfeljebb mennyiségű információt nyerhetünk és a hiányzó információ ezért várhatóan nagyobb lesz, mint

4.17. Tétel. Az alternatívás keresési stratégiára

Bizonyítás. Tekintsünk egy tetszőleges kódfát, és legyen a kódfa olyan szögpontja, amely nem végpont. Jelölje az -ból kiinduló élek végpontjait. A megfelelő halmazokat is jelöljük ugyanígy. Legyen

ekkor a valószínűséget az végponthoz vezető ág minden, a végponttól különböző szögpontjához odaírva, és áganként összegezve közvetlenül kapjuk, hogy

ahol az összegzést a végpontoktól különböző szögpontokra kell elvégezni.

Mivel éppen annak a valószínűsége, hogy a keresés során eljutunk az szögpontba, az szögpontban végzendő kísérlet kimeneteinek valószínűsége rendre ahol

Ennek a kísérletnek az entrópiája tehát

Számoljuk ki a

mennyiséget, ahol az összegzést a kódfa végponttól különböző szögpontjaira kell elvégezni. A felbontás azt mutatja, hogy ebben az öszzegben, a kezdőpont és a végpont kivételével minden szögponthoz a

kifejezés egyszer pozitív, egyszer negatív előjelű, mert egyszer típusú egyszer pedig típusú.

Tehát az összegzés

Viszont az entrópia tulajdonságai alapján

Tehát

amelyből adódik az állítás.

4.18. Megjegyzés. Jól látható, hogy az alsó korlátot akkor közelítjük meg, ha minden lépésben az egyenletes elszláshoz közel eső alternatívás lépést alkalmazunk.

Jelölés: A kódolás esetén a kódszó hossza.

4.19. Definíció. A kód prefix, ha a kódszavak mind különbözőek és egyik kódszó sem folytatása a másiknak.

4.20. Megjegyzés. Az állandó kódhosszú kód mindig prefix, ha a kódszavai különbözőek. A prefix kódhoz kódfa rendelhető, s így közvetlen kapcsolatban van a keresési stratégiákkal.

4.21. Tétel. Minden prefix kód egyértelműen dekódolható.

Bizonyítás. A kód prefix, azaz a kódszavak mind különbözőek és egyik kódszó sem folytatása a másiknak. Tételezzük fel, hogy létezik egy üzenet, amely kétféleképpen dekódolható. Az ilyen üzenetek között van legrövidebb, s ekkor feltételezve, hogy létezik két különböző kódszavakra bontás, az első kódszavaknak rögtön különbözőknek kell lenniük. Viszont ekkor az egyik folytatása a másiknak (egyforma hosszúak nem lehetnek). Ez ellentmond annak, hogy a kód prefix.

4.22. Megjegyzés. A Sardinas-Patterson módszer alkalmazása esetén prefix kódra

4.23. Lemma. A kódfák és a prefix kódok között kölcsönös egy-egyértelmű megfeleltetés van.

4.24. Megjegyzés. A prefix kód átlagos kódhossza nem lehet kisebb, mint

4.25. Tétel. (Kraft-Fano egyenlőtlenség) Ha számú kódjelből készített prefix kód, akkor

ahol a kódszó hossza.

Bizonyítás. Legyen Minden kódszót egészítsünk ki hosszúvá. kiegészítése -féleképpen lehetséges. Tehát

amelyből adódik az állítás.

4.26. Tétel. (Kraft-Fano egyenlőtlenség megfordítása) Ha az

természetes számok eleget tesznek a

egyenlőtlenségnek, ahol természetes szám, akkor létezik kódjelből alkotott prefix kód, melynél a kódszó hossza éppen

Bizonyítás. Legyen ekkor

Legyen a teljes kódfa, amelyben minden ág hosszú. Válasszunk ki egy ágat, amelyből élet elhagyunk stb. Teljes indukcióval adódik az állítás.