InfElmTetel44

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

LZ77: A kódoló a forrásszimbólumok sorozatát egy $h_{a}$ hosszú csúszóablakon keresztül vizsgálja. Ez két részből áll: a keresőpufferből, mely a legutóbb kódolt $h_{k}$ db. forrásszimbólumot tartalmazza és az előretekintő pufferből, mely pedig a kódolandó $h_{e}$ db. szimbólumot. $h_{a}=h_{k}+h_{e}$ A kódoló a keresőpufferben megkeresi az előretekintő puffer első szimbólumával megegyező szimbólumokat. Ehhez egy hátrafelé haladó mutatót használ. Megnézi, hogy a keresőpufferben lévő szimbólumok milyen hosszan egyeznek meg az előretekintő puffer szimbólumaival és azt választja ki, ahonnan kezdve leghosszabb az egyezés. A kódoló elküld egy (t,h,c) hármast, ahol: t: a keresőpufferben megtalált szimbólum távolsága az előretekintő puffertől, offset h: a kereső- és az előretekintő puffer egyező szimbólumainak legnagyobb hosszúsága c: az első, előretekintő pufferben lévő nem egyező karakter kódszava Amennyiben nem találunk egyezést: t=h=0 Egy hármas kódolásához állandó hosszúságú kód használatával $logh_{k}+logh_{e}+log|X|$ bit szükséges (pontosabban a felső egészrészeik összege), ahol |X a kódábécé elemszáma.

LZ78: A kódoló és a dekódoló is szótárt épít az előzőleg előfordult sorozatokból. A kódoló megkeresi a forrásszimbólumok aktuális pozíciójától kezdődő lehosszabb egyezést a szótárban. Átküld egy (i,c) párt, ahol i az egyező karaktersorozat szótárbeli indexét jelöli, c pedig az első nem egyező karakter kódja. Ezután felveszi a szótárba az i indexű egyező karaktersorozat és a c karakter konkatenációjaként kapott sztringet és a következő szabad indexet adja neki. Ha nem talál egyező karaktersorozatot a szótárban, akkor a (0,c) párost küldi át. Megmutatható, hogy az LZ78 egy betűre jutó átlagos kódszóhossza konvergál ${\frac {H(X)}{logs}}$-hez minden stacionárius és ergodikus forrásra.

LZW: Hasonló az LZ78-hoz, de megtakarítjuk az (i,c) párból c elküldését, tehát csak szótárbeli indexeket küld át. Ehhez szükséges, hogy a szótárban már kiinduláskor szerepeljen az összes egybetűs szimbólum a forrásábécéből. Itt is addig olvassuk be a szimbólumokat a p pufferbe, míg egyezést találunk egy szótárbeli elemmel. Ha a az első olyan karakter, melyre pa már nincs benne a szótárban, akkor átküldjük p indexét, a pa sorozatot fevesszük új szótárbejegyzésként és az a karaktertől kezdve folytatjuk az eljárást.

-- pikopeti - 2007.06.13.