LZ77

A Wikipédiából, a szabad enciklopédiából

Az LZ77 veszteségmentes tömörítőalgoritmus, amit Abraham Lempel és Jacob Ziv publikált 1977-ben (ezt jelöli a névben szereplő 77-es szám). Az algoritmust a szerzőpáros egy évvel később továbbfejlesztette LZ78 néven.

Az idők folyamán többen készítettek ennek az eljárásnak az alapján tömörítő algoritmusokat, mint például a James Storer és Thomas Szymanski nevéhez fűződő LZSS, a Terry Welch által bemutatott LZW és az Igor Pavlov jegyezte LZMA algoritmus.

Az algoritmus működése[szerkesztés]

Az LZ77 egy szótár alapú tömörítő eljárás, amely egy meghatározott méretű (4-64 kilobyte) úgynevezett csúszó ablakon keresztül vizsgálja a kódolandó adatfolyamot. A tömörítési folyamat során egy keresőpufferben letárolja az n db utolsó byte-ot, és amikor egy olyan byte-csoportot talál, mely szerepel ebben a pufferben, akkor a byte-csoport helyett annak a pufferben lévő helyét és hosszát tárolja le.

Példa[szerkesztés]

Bemeneti adatfolyam
pozíció 1 2 3 4 5 5 7 8 9
karakter A A B C B B A B C

A kódolási folyamat menete:

  1. A pozíció beállítása az adatfolyam elejére;
  2. megkeresi a leghosszabb korábbi előfordulást;
  3. kimenetre írja a (B, L) C formulát, ahol B a megtalált karakter távolsága az előretekintő puffertől, az L az egyező karakterek legnagyobb hosszúsága, a C pedig az első nem egyező karakter az előretekintő pufferben;
  4. ha az előretekintő puffer nem üres, akkor eltolja a pozíciót (ablakot) az L+1-el, majd visszaugrik a 2. lépésre.
Kódolási folyamat
lépés pozíció találat karakter kimenet
1. 1 - A (0,0) A
2. 2 A B (1,1) B
3. 4 - C (0,0) C
4. 5 B B (2,1) B
5. 7 A B C (5,2) C

Források[szerkesztés]