LZ77
Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.
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 [math] h_a [/math] 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 [math] h_k [/math] betűt tartalmazó rész
* az előretekintő puffer, ami a következő [math] h_e [/math] betűt tartalmazza.
[math] h_a = h_k + h_e [/math]
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 [math] \lt t,h,c \gt [/math] hármast, ahol
* [math] t [/math] 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 [math] \lceil log h_k \rceil + \lceil log h_e \rceil + \lceil log |\chi| \rceil [/math] bit szükséges, ahol [math] | \chi | [/math] 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 [math]\frac{H(X)}{log s}[/math]-hez, ha ([math] h_e, h_k \rightarrow \infty [/math]) .
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.
