Movatterモバイル変換


[0]ホーム

URL:


跳转到内容
维基百科自由的百科全书
搜索

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 like45: 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.
理论
无损数据压缩
熵編碼
字典編碼英语Dictionary coder
其他
有损数据压缩
变换编码
预测编码
音频
概念
编解码组件
图像
概念
方法
视频
概念
编解码组件
检索自“https://zh.wikipedia.org/w/index.php?title=LZSS&oldid=78904914
分类:​

[8]ページ先頭

©2009-2025 Movatter.jp