Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZ77}} ==LZ77== ===LZ77 kódolás=== Az információforrás vizsgálata egy $h_a$ hosszúságú csúszóablakon keresztül tö…”

2012-10-21T20:02:16Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZ77}} ==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ö…”

Új lap

{{GlobalTemplate|Infoalap|LZ77}}

==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> < t,h,c > </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.

-- [[NeoXon|NeoXon]] - 2005.12.01.
-- [[SzelessZoltanTamas|Sales]] - 2006.06.24.

[[Category:Infoalap]]

LZ77 - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZ77}} ==LZ77== ===LZ77 kódolás=== Az információforrás vizsgálata egy h_a hosszúságú csúszóablakon keresztül tö…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|LZ77}} ==LZ77== ===LZ77 kódolás=== Az információforrás vizsgálata egy $h_a$ hosszúságú csúszóablakon keresztül tö…”