LZSS ( Lempel-Ziv-Storer-Szymanski , Lempel-Ziv-Storer-Szymansky [1] ) je bezeztrátový algoritmus komprese dat odvozený od metody LZ77 . Vytvořeno v roce 1982 Jamesem Storerem a Thomasem Szymanskim. LZSS byla popsána v článku "Datakomprese prostřednictvím textové substituce" (komprese dat prostřednictvím textové substituce), publikovaném v časopise ACM (1982, PP. 928-951). [2]
LZSS je metoda komprese slovníku. Snaží se nahradit opakované sekvence znaků odkazem na slovník.
Hlavní rozdíl mezi původním LZ77 a LZSS je v tom, že v metodě LZ77 může být záznam slovníkového odkazu delší než řetězec, který nahrazuje (to znamená, že zadáním takového odkazu je komprimovaný fragment delší než nekomprimovaný) . V metodě LZSS jsou takové odkazy vynechány, pokud je délka řetězce menší než některé nastavení ("break even"). Navíc LZSS používá jednobitový příznak k označení, zda další fragment komprimovaného proudu je literál (bajt) nebo slovníkový odkaz (pár délky a offsetové hodnoty).
Mnoho populárních archivátorů 90. až 20. století, jako jsou PKZip , ARJ , RAR , ZOO , LHarc , používá metodu LZSS místo LZ77 jako hlavní algoritmus pakování dat. Schémata kódování pro literály a páry s offsetem délky se často liší, ale populárnější je entropické kódování pomocí Huffmanova kódu . Mnoho implementací je založeno na kódu Haruhiko Okumury z roku 1989. [3] [4]
Vstupní text, 177 bajtů:
0: Já jsem Sam 9: 10: Jsem Sam 19: 20: Ten Sam-já-jsem! 35: Ten Sam-já-jsem! 50: Nelíbí se mi 64: ten Sam-já-jsem! 79: 80: Máte rádi zelená vejce a šunku? 112: 113: Nemám je rád, Sam-já-jsem. 143: Nemám rád zelená vejce a šunku.Při minimální shodě dvou bajtů získáme 94 bajtů (vyjma 12 bajtů příznaků typu fragmentu). Páry (odsazení, délka) jsou uvedeny v závorkách:
0: Já jsem Sam 9: 10: (5,3) (0,4) 16: 17: To(4,4)-já-jsem!(19,16)Nelíbí se mi 45: t(21,14) 49: Máte (58,5) zelená vejce a šunku? 78: (49,14) jim, (24,9). (112,15) (92,18).
Zdrojový kód pro implementaci algoritmu LZSS
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||