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
+ 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: A pozíció beállítása az adatfolyam elejére; megkeresi a leghosszabb korábbi előfordulást; 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; 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 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
Kategória:Tömörítő algoritmusok