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
[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]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, aholB
a megtalált karakter távolsága az előretekintő puffertől, azL
az egyező karakterek legnagyobb hosszúsága, aC
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.
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 |