Hogyan működik az LZSS tömörítési algoritmus
Az LZ betűpár a névben a Lempel-Ziv párosra, az SS betűpár pedig a Storer-Szymanski párosra vonatkozik. Ez az algoritmus a "visszanéző" puffer (az utóbb letömörített n db byte-ot tartalmazza) mellett még egy "előrenéző" puffert is alkalmaz, melybe a letömörítendő byte-ok kerülnek.
Az algoritmus megkeresi a letömörítendő byte-ok és a "visszanéző" puffer leghosszabb egyezését, s ha annak hossza meghaladja a minimálisnak definiált, általában 3 byte-ot, akkor egy pozíció, hossz párt tárol le. Megoldandó probléma még, hogy ennyiből a kitömörítő még nem tudná megállapítani, hogy a következő kód egy egyszerű byte-e, vagy pedig egy pozíció, hossz páros. Ezt az RLE-nél alkalmazott, az előzőekben leírt, módszerekkel is megvalósíthatnánk, azonban a tapasztalat szerint egyszerűbb és jobb, ha minden kód elé egy plusz bitet írunk ki, mely azt jelzi, hogy a soron következő adat byte, vagy visszautaló kódpár. (A gyakorlatban ezeket a biteket 8-asával tárolják a könnyebb kezelhetőség érdekében, azonban ez a lényegen nem változtat. )
Az algoritmus vázlata a következő:
- Ciklus amíg "előrenéző" puffer nem üres
- EgyezésKeres(pozíció, hossz) [a maximum egyezés keresése]
- Ha hossz>minimum_hossz akkor
- Kiír(pozícó,hossz)
- különben
- Kiír(KövByte)
- Elágazás vége
- Ciklus vége
Az algoritmus több ötlettel is javítható, gyorsítható, pl. javulhat a tömörítés aránya, ha a következő pozícióra is megvizsgáljuk az egyezést, gyorsul a tömörítés, ha keresés során ún. HASH táblát alkalmazunk, stb. Mivel az algoritmus könnyen megvalósítható és jól tömörít, így gyorsan elterjedt.
forrás: internet
