LZSS

Lempel–Ziv–Storer–Szymanski（LZSS）是一個無失真資料壓縮演算法，屬於LZ77的衍生，1982年由James Storer和Thomas Szymanski（英語：Thomas_Szymanski）建立。LZSS發布於《Journal of the ACM》^[1]的「Data compression via textual substitution」。^[2]

LZSS是一種字典編碼技術。它會嘗試以符號字串替換相同字串為一個字典位置的參照。

LZ77與LZSS的主要區別是，LZ77的字典參照可能比受替換的字串更長。在LZSS中，如果長度小於「盈虧平衡」點，參照會被省略。此外，LZSS使用單位元標誌標記下一個資料塊是原文（位元組）還是參照的偏移與長度。

例子

此例是Dr. Seuss所著《Green Eggs and Ham（英語：Green_Eggs_and_Ham）》的開頭，每行開頭的已有字元總數是為方便所設。

  0: I am Sam
  9:
 10: Sam I am
 19:
 20: That Sam-I-am!
 35: That Sam-I-am!
 50: I do not like
 64: that Sam-I-am!
 79: 
 80: Do you like green eggs and ham?
112:
113: I do not like them, Sam-I-am.
143: I do not like green eggs and ham.

這是該段文字在未壓縮形式的177位元組。假設盈虧平衡點是2位元組（並因此是2位元組的指標/偏移對），那麼加上一位元組的新行字元，此文字使用LZSS壓縮後將變為94位元組：

 0: I am Sam
 9:
10: (5,3) (0,4)
16:
17: That(4,4)-I-am!(19,16)I do not like
45: t(21,14)
49: Do you(58,5) green eggs and ham?
78: (49,14) them,(24,9).(112,15)(93,18).

注意：這不包括標記下一個文字塊是指標或原文的12位元組。如果加上它，該段文字變為106位元組，仍會少於原文的177位元組。

實現

許多流行的存檔格式如PKZip（英語：PKZip）、ARJ、RAR、ZOO（英語：Zoo_(file_format)）、LHarc都使用LZSS而不是LZ77作為主要的壓縮演算法；原文字元和長度距離對的編碼方式各有不同，最常見的選項是霍夫曼編碼。大多數實現源於1989年日本學者奧村晴彥所開發的代碼。^[3][4]Allegro程式庫第四版可以編碼和解碼LZSS格式^[5]，但該特性在第五版中被去除。Game Boy Advance BIOS可以解碼一個稍作修改的LZSS格式。^[6]

參見

• LZ77
• LZW

參考資料

1. （1982年，928頁至951頁）
2. Storer, James A.; Szymanski, Thomas G. (October 1982).
3. Simtel.net mirror.
4. Haruhiko Okumura.
5. Hargreaves, Shawn, et al.
6. Korth, Martin.