Lempel–Ziv–Storer–Szymanski（LZSS）は、 LZ77の派生であるロスレスデータ圧縮 アルゴリズムであり、1982年にJames A. StorerとThomas Szymanskiによって考案されました。LZSSは、 Journal of the ACM （1982年、928～951ページ）に掲載された論文「Data compression via textual replacement」で説明されています。[1]
LZSSは辞書コーディング技術です。これは、記号の文字列を、辞書内の同じ文字列への参照に置き換えようとするものです。
LZ77とLZSSの主な違いは、LZ77では辞書参照が置換対象の文字列よりも長くなる可能性があることです。LZSSでは、長さが「損益分岐点」よりも短い場合、そのような参照は省略されます。さらに、LZSSでは1ビットのフラグを使用して、次のデータチャンクがリテラル（バイト）なのか、オフセットと長さのペアへの参照なのかを示します。
例
これはドクター・スースの『グリーン・エッグス・アンド・ハム』の冒頭部分です。便宜上、行頭に文字番号を付しています。『グリーン・エッグス・アンド・ハム』はLZSS圧縮の好例です。なぜなら、この本は単語数が170語であるにもかかわらず、固有の単語はわずか50語しかないからです。 [2]つまり、単語は繰り返されていますが、連続していません。
0: 私はサムです 9: 10: サム・アイ・アム 19: 20: あのサム・アイ・アム！ 35: あのサム・アイ・アム！ 50: 好きではない 64: あのサム・アイ・アム！ 79: 80: グリーンエッグスアンドハムは好きですか? 112: 113: 私は彼らが好きではありません、サム・アイ・アム。 143: 私はグリーンエッグスアンドハムが好きではありません。
このテキストは圧縮されていない状態では177バイトです。損益分岐点を2バイト（つまりポインタ/オフセットペアが2バイト）とし、改行文字を1バイトとすると、LZSSで圧縮されたこのテキストは95バイトになります。
0: 私はサムです 9: 10: (5,3) (0,4) 16: 17: それが(4,4)-私-です!(19,15) 32: 好きではない 46: t(21,14) 50: グリーンエッグスアンドハムはお好きですか? 79: (49,14) 彼ら、(24,9).(112,15)(92,18).
注: この値には、次のテキストがポインタかリテラルかを示す11バイトのフラグは含まれていません。これを追加すると、テキストの長さは106バイトになりますが、それでも元の177バイトより短くなります。
実装
ARJ、RAR、ZOO、LHarcなどの多くの一般的なアーカイバは、主要な圧縮アルゴリズムとして LZ77 ではなく LZSS を使用します。リテラル文字と長さと距離のペアのエンコードはさまざまですが、最も一般的なオプションはハフマン符号化です。ほとんどの実装は、 1989 年にHaruhiko Okumuraがパブリック ドメインで公開したコードに由来しています。[3] [4] Allegro ライブラリのバージョン 4 はLZSS 形式のエンコードとデコードが可能ですが、[5]その機能はバージョン 5 では削除されました。 Game Boy Advance BIOS は、わずかに変更された LZSS 形式をデコードできます。[6] Apple のmacOS は、カーネル コードの圧縮方法の 1 つとして LZSS を使用します。[7]
参照
- レンペル・ジヴ・ウェルチ（LZW）
参考文献
- ^ Storer, James A.; Szymanski, Thomas G. (1982年10月). 「テキスト置換によるデータ圧縮」. Journal of the ACM . 29 (4): 928– 951. doi : 10.1145/322344.322346 .
- ^ 「ドクター・スースの物語の裏に隠された10の物語」CNN、2009年1月23日。2009年1月26日閲覧。
- ^ Simtel.netミラーサイト。1989年の奥村晴彦による実装。1999年2月3日アーカイブ。
- ^ 奥村晴彦. 日本におけるデータ圧縮の歴史. 2016年1月10日アーカイブ.
- ^ Hargreaves, Shawn 他. Allegro ソースコード: lzss.c. 2016年7月13日にアクセス.
- ^ Korth, Martin. 「GBATEK LZ Decompression Functions」. problemkaputt.de . 2022年6月7日閲覧。
- ^ "kext_tools/compression.c". GitHub . Apple Open Source . 2019年12月28日閲覧。
