LZSS ( Lempel-Ziv-Storer-Szymanski , Lempel-Ziv-Storer-Szymansky [1] ) on häviötön tiedonpakkausalgoritmi, joka on johdettu LZ77 -menetelmästä . Luonut vuonna 1982 James Storer ja Thomas Szymanski. LZSS kuvattiin artikkelissa "Data compression via textual substitution" (tietojen pakkaus tekstin korvaamisen kautta), joka julkaistiin ACM-lehdessä (1982, PP. 928-951). [2]
LZSS on sanakirjan pakkausmenetelmä. Se yrittää korvata toistuvat merkkijonot sanakirjaviitteellä.
Suurin ero alkuperäisen LZ77:n ja LZSS:n välillä on, että LZ77-menetelmässä sanakirjaviitteen syöttö voi olla pidempi kuin sen korvaama merkkijono (eli tällaisen viittauksen syöttäminen tekee pakatusta fragmentista pidemmän kuin pakkaamaton). . LZSS-menetelmässä tällaiset viittaukset jätetään pois, jos merkkijonon pituus on pienempi kuin jokin asetus ("break even"). Lisäksi LZSS käyttää yhden bitin lippua osoittamaan, onko pakatun virran seuraava fragmentti literaali (tavu) vai sanakirjaviittaus (pituus- ja offset-arvopari).
Monet suositut 1990-2000-lukujen arkistaattorit, kuten PKZip , ARJ , RAR , ZOO , LHarc , käyttävät LZSS-menetelmää LZ77:n sijaan pääasiallisena datan pakkausalgoritmina. Literaalien ja pituussiirtymäparien koodausmenetelmät eroavat usein, mutta Huffman-koodia käyttävä entropiakoodaus on suositumpaa . Monet toteutukset perustuvat Haruhiko Okumuran koodiin vuodelta 1989. [3] [4]
Syötä teksti, 177 tavua:
0: Olen Sam 9: 10: Sam olen 19: 20: Se Sam-I-am! 35: Se Sam-I-am! 50: En pidä 64: se Sam-I-am! 79: 80: Pidätkö vihreistä munista ja kinkusta? 112: 113: En pidä niistä, Sam-I-am. 143: En pidä vihreistä munista ja kinkusta.Kahden tavun vähimmäissovituksella saamme 94 tavua (lukuun ottamatta 12 tavua fragmenttityyppisiä lippuja). Parit (offset, pituus) on merkitty suluissa:
0: Olen Sam 9: 10: (5.3) (0.4) 16: 17: Tuo(4,4)-minä olen!(19,16)En pidä 45: t(21,14) 49: Oletko(58,5) vihreitä munia ja kinkkua? 78: (49.14) ne,(24.9).(112.15)(92.18).
Lähdekoodi LZSS-algoritmin toteuttamiseen
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||