跳至內容

LZSS

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

Lempel–Ziv–Storer–SzymanskiLZSS)是一個無損數據壓縮算法,屬於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英語PKZipARJRARZOO英語Zoo_(file_format)LHarc都使用LZSS而不是LZ77作為主要的壓縮算法;原文字符和長度距離對的編碼方式各有不同,最常見的選項是霍夫曼編碼。大多數實現源於1989年日本學者奧村晴彥所開發的代碼。[3][4]Allegro程序庫第四版可以編碼和解碼LZSS格式[5],但該特性在第五版中被去除。Game Boy Advance BIOS可以解碼一個稍作修改的LZSS格式。[6]

參見

[編輯]

參考資料

[編輯]
  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.