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