Tartalomjegyzék

< Algoritmusok

LZ77

Az LZ77-ről

Abraham Lempel és Jakob Ziv publikálta 1977-ben. Innen a neve, bár LZ1 néven is használták.

Toló- vagy csúszóablakos tömörítés.

Egy k hosszúságú ablakot használunk, amelyet végigcsúsztatunk a tömörítendő karaktersorozaton. A k ablak két részből áll. Egy hk hosszúságú keresőablakból és egy he hosszúságú előremutató ablakból.

Példa

TONINITONINIT
lépés kimenet
1 0, 0, T
2 0, 0, O
3 0, 0, N
4 0, 0, I
5 2, 2 ,T
6 6, 6, *

Példa részletesen

Legyen egy karaktersorozat a példa kedvéért:

TONINITONINIT

A kódolása:

Legyenek a következő ablak méretek:

        TONINITONINIT
^              ^
   teljes ablak

A kereső és az előremutató ablak ekkor:

        TONINITONINIT
^      ^^      ^
|      ||      |
 kereső  előrem.

Vegyük az előremutató ablak első karakterét:

        TONINITONINIT
        ^
|      ||      |
 kereső  előrem.

Ez „T” betű. Megkeressük a keresőablakban van-e ilyen karakter, a keresőablakban visszafele haladva. A keresőablak üres, így csak lekódoljuk magát a T betűt. A kód kimenete három érték. Általánosan felírva:

index, hossz, karakter

Az első kódkimenet ezek alapján:

<0, 0, T>

Az egész ablakot eltoljuk jobbra eggyel:

        TONINITONINIT
         ^
 |      ||      |
  kereső  előrem.

A következő az „O” betű. A keresőablakban nincs ilyen betű, ezért ezt is csak felírjuk:

<0, 0, T>
<0, 0, O>

Az egész ablakot eltoljuk jobbra eggyel:

        TONINITONINIT
          ^
  |      ||      |
   kereső  előrem.

Az „N” betűvel az előbbiekhez hasonlóan járok el:

<0, 0, T>
<0, 0, O>
<0, 0, N>

Az „I” betűvel is:

<0, 0, T>
<0, 0, O>
<0, 0, N>
<0, 0, I>

A keresőablakunk, most egy olyan betűhöz ért, ami szerepel a keresőablakban.

        TONINITONINIT
            ^
    |      ||      |
     kereső  előrem.

Felírjuk, a keresőablakban visszafele hányadik helyen van az „N” betű. A számozást eggyel kezdem. Így a második helyet kell felírnunk. Felírjuk a kettőt:

<2, . , .>

A másik két érték még kérdéses.

Megnézzük, hogy hány karakter egyezik N-től a kereső és az előremutató ablakban. Egyezés „NI”:

TONINITONINIT
  ^^^^

Amit kimenetként felírunk:

<2, 2 , T>

A harmadik helyre felírjuk az előremutató ablakban a következő nem egyező karaktert:

TONINITONINIT
      ^

A kódunk most így néz ki:

<0, 0, T>
<0, 0, O>
<0, 0, N>
<0, 0, I>
<2, 2 ,T>

A következő karaktert vesszük ez egy „O” betű:

TONINITONINIT
       ^

Nézzük, hol tart az ablak:

        TONINITONINIT
               ^
       |      ||      |
        kereső  előrem.

Az „O” betű szerepel a keresőablakban, visszafele a 6-s helyen. Hat egyezés van. Elfogytak a karakterek, így vége van.

A kódunk most így néz ki:

<0, 0, T>
<0, 0, O>
<0, 0, N>
<0, 0, I>
<2, 2 ,T>
<6, 6, *>

Segédeszköz

Gyakorlat

Feladat 001

Dekódolja a következő kódot:

0,0,p
0,0,a
0,0,r
0,0,k
0,0,o
0,0,l
0,0,á
0,0,s
0,0,_
0,0,a
2,1,p
3,1,r
0,0,k
0,0,b
4,1,n
0,0,_
0,0,p
4,1,t
2,1,k
6,1m
0,0,e
0,0,l
1,1,e
0,0,t
1,1,null