LZ77

• Szerző: Sallai András
• Copyright © 2014, Sallai András
• Szerkesztve: 2014, 2019, 2020
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

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 h_k hosszúságú keresőablakból és egy h_e hosszúságú előremutató ablakból.

TONINITONINIT

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

TONINITONINIT

A kódolása:

Legyenek a következő ablak méretek:

• h = 16
• h_k = 8
• h_e = 8

        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 index, ha a keresőablakban volt ilyen karakter, akkor annak helye, ellenben 0
• A hossz, ha a keresőablakban volt ilyen karakter, akkor hány további karakter egyezik az előremutató és a keresőablakban.
• Ha nem volt egyezés felírjuk a karaktert, ha volt felírjuk az első nemegyező karaktert

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, *>

• https://szit.hu/lz

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