LZ77

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

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

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.

Források

• Miskolci Egyetem Gépészmérnöki és Informatikai Kar Informatikai és villamosmérnöki tanszékcsoport
• A VIK Wikiből: InfElmTetel44
• A Universal Algorithm for Sequential Data Compression (1977) by Jacob Ziv , Abraham Lempel

Ez az informatikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!