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

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

• 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