LZ77

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

LZ77 kódolás

Az információforrás vizsgálata egy $h_{a}$ hosszúságú csúszóablakon keresztül történik.
Ez két részre van bontva:
* a keresőpufferen a már kódolt $h_{k}$ betűt tartalmazó rész
* az előretekintő puffer, ami a következő $h_{e}$ betűt tartalmazza.
$h_{a}=h_{k}+h_{e}$

TODO: ÁBRA

A kódoló a keresőpufferben megkeresi az előretekintő puffer első karakterének előfordulásait. Megnézi, hogy megtalált pozíciókkal kezdődően, a keresőpufferben lévő szimbólumok milyen hosszan egyeznek az előretekintő puffer szimbólumaival, és a találatok közül azt választja ki, amelytől kezdve a leghosszabb az egyezés.

A kódoló ezután 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 pedig az első, az előretekintő pufferben lévő nem egyező szimbólum kódszava.

TODO: ÁBRA

Azért küldjük el az első nem egyező karakter kódját is, hogy kezeljük azt az esetet, amikor az előretekintő puffer szimbólumait nem találjuk a keresőpufferben. Ilyenkor t és h értéke 0.

Egy hármas kódolásához állandó hosszúságú kód használatával $\lceil logh_{k}\rceil +\lceil logh_{e}\rceil +\lceil log|\chi |\rceil$ bit szükséges, ahol $|\chi |$ a forrásábécé mérete. Megmutatható, hogy az eljárás hatékonysága aszimptotikusan megközelíti az optimális algoritmusét, amely előzetesen ismeri a forráseloszlást, azaz stacionárius és ergodikus forrás esetén az átlagos kódszóhossz konvergál ${\frac {H(X)}{logs}}$-hez, ha ($h_{e},h_{k}\rightarrow \infty$) .

LZ77 dekódolás

< t, h, c > alakú hármasokat fogadunk, majd ez alapján bővítjük a keresőpuffert a dekódoló oldalon.

t: keresőpufferbeli illeszkedés kezdete (jobbról számított ennyi karakter)
h: keresőpufferbeli illeszkedés hossza karakterben
c: az illeszkedés utáni első karakter kódja

A dekódolás során csak a keresőpufferben levő karakterek ismertek, az előretekintő pufferben lévőkről csak a kódoló tud. Először, amíg a keresőpuffer üres, <0, 0, f(x)> alakú hármasok érkeznek csak, ahol x a forrásábécé eleme, f(x) pedig a kódja - f(x) a kódábécé eleme.

Ha már van olyan elem a keresőpufferben, amely az előretekintő pufferben épp érkezik, akkor van értelme illeszkedést vizsgálni a kódoló oldalon. A dekódoló oldali illeszkedésekre ekkor az alábbi két eset lehetséges:

a) nincs átlógás

Tegyük fel, hogy már dekódoltuk a ccabrar sztringet. Ha ekkor jön egy <4, 2, f(c)> hármas, akkor ez azt jelenti, hogy a 2 dekódolandó karakter a keresőpuffer jobb oldalától 4 karakter távolságnyira kezd és 2 hosszú az illeszkedés, majd pedig az illeszkedést egy c karakter zárja. Így tehát a "ccabrar" keresőpuffer alapján a következőt dekódoljuk: "brc", hiszen jobbról a 4. karakter a 'b' és kettő hosszan a "br" sztring illeszkedik, ezt pedig lezárjuk a 'c' karakterrel. A keresőpuffer ezután tehát a következő lesz: ccabrarbrc.

b) van átlógás a keresőpufferből az előretekintő pufferbe

Térjünk vissza a jó kis ccabrar tartalmú keresőpufferünkhöz. Előfordulhat, hogy a kódoló oldalon egy olyan illeszkedés van, amely átnyúlik a keresőpufferből az előretekintő pufferbe. Tehát pl. ccabrar|rarrad, ahol jelöli a két puffer közti választóvonalat. Ez esetben nem csak a <3, 3, f(r)> -t fogjuk kódolni, hiszen ha megfigyeljük, akkor az illeszkedés ennél hosszabb is lehet: "rarra". Ilyenkor tehát előfordulhat, hogy olyan < t, h , c > hármast küldünk át, ahol h értéke meghaladja t értékét, jelen esetben <3, 5, f(d)>.
A dekódolásnál azt gondolhatnánk, hogy zsákutcába értünk, hiszen honnan tudhatnánk mi az a fennmaradó 2 karakter, ami átnyúlt a kódoló oldalon az előretekintő pufferbe. Szerencsére van rá módszer, hogy ezt kitaláljuk, ugyanis ez a két karakter nem lehetett más, mint a keresőpufferben illeszkedő minta első két karaktere, vagyis a "rar" szting első két karaktere. Hogy miért van így? Azért, mert máskülönben nem csak 5 hosszan, de semmilyen hosszan nem tudott volna illeszkedni a kódoló oldalon az előretekintő puffer első (néhány) karaktere a keresőpufferbeli betűkkel. Vegyük pl. ccabrar|rarrad helyett a ccabrarefrrad példát, vagyis most a "két átlógó karakter" nem egyezik a keresőpufferbeli illeszkedés első 2 karakterével. Jól látszik, hogy ebben az esetben semmilyen illeszkedés sem lenne, tehát <0, 0, f(e)> -t küldenénk el.
Így tehát lefedtünk minden esetet, tehát a dekódolás lehetséges kizárólag az átküldött hármasok segítségével.

-- NeoXon - 2005.12.01. -- Sales - 2006.06.24.