LZSS ( Lempel-Ziv-Storer-Szymanski , Lempel-Ziv-Storer-Szymansky [1] ) er en tabsfri datakomprimeringsalgoritme afledt af LZ77 -metoden . Skabt i 1982 af James Storer og Thomas Szymanski. LZSS blev beskrevet i artiklen "Data compression via textual substitution" (data compression through textual substitution), publiceret i tidsskriftet ACM (1982, PP. 928-951). [2]
LZSS er en ordbogskomprimeringsmetode. Den forsøger at erstatte gentagne tegnsekvenser med en ordbogsreference.
Hovedforskellen mellem den originale LZ77 og LZSS er, at i LZ77-metoden kan indtastningen af en ordbogsreference være længere end den streng, den erstatter (det vil sige, at indtastningen af en sådan reference gør det komprimerede fragment længere end det ukomprimerede) . I LZSS-metoden udelades sådanne referencer, hvis længden af strengen er mindre end en eller anden indstilling ("break even"). Desuden bruger LZSS et one-bit flag til at angive, om det næste fragment af den komprimerede strøm er en literal (byte) eller en ordbogsreference (længde og offset værdipar).
Mange populære arkivere fra 1990'erne - 2000'erne, såsom PKZip , ARJ , RAR , ZOO , LHarc bruger LZSS-metoden i stedet for LZ77 som den primære datapakningsalgoritme. Kodningsskemaer for bogstaver og længde-offset-par er ofte forskellige, men entropikodning ved hjælp af Huffman-koden er mere populær . Mange implementeringer er baseret på kode af Haruhiko Okumura fra 1989. [3] [4]
Input tekst, 177 bytes:
0: Jeg er Sam 9: 10: Sam jeg er 19: 20: Den Sam-jeg-er! 35: Den Sam-jeg-er! 50: Jeg kan ikke lide 64: den Sam-jeg-er! 79: 80: Kan du lide grønne æg og skinke? 112: 113: Jeg kan ikke lide dem, Sam-jeg-er. 143: Jeg kan ikke lide grønne æg og skinke.Med et minimumsmatch på to bytes får vi 94 bytes (eksklusive 12 bytes af fragmenttypeflag). Par (offset, længde) er angivet i parentes:
0: Jeg er Sam 9: 10: (5,3) (0,4) 16: 17: Det(4,4)-jeg-er!(19,16) kan jeg ikke lide 45: t(21,14) 49: Har du(58,5) grønne æg og skinke? 78: (49.14) dem,(24.9).(112.15)(92.18).
Kildekoden til implementering af LZSS-algoritmen
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||