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