LZW

✍ dations ◷ 2025-07-08 19:02:29 #LZW

蓝波-立夫-卫曲编码法(Lempel-Ziv-Welch,缩写LZW),是以色列科学家亚伯拉罕·蓝波(英语:Abraham Lempel)(希伯来语:אברהם למפל‎)、杰可布·立夫(英语:Jacob Ziv)( יעקב זיו‎)与美国学者泰瑞·卫曲(英语:Terry Welch)(Terry Welch)共同提出的一种无损数据压缩算法。

它在1984年由泰瑞·卫曲改良亚伯拉罕·蓝与杰可布·立夫在1978年发表的LZ78的版本而来(主要是基于蓝波、立夫的压缩概念,设计出一套具有可逆推的逻辑程序)。

与霍夫曼编码相比,蓝波-立夫-卫曲编码法被视作将不同长度字符串以固定长的码编辑(霍夫曼编码将固定长度字符用不同长度的码编辑)。其优点在于此方法只需存储一个相当小的表格,即可存储资料还原时相对应的值,所以所需成本相对地低;然而,这种算法的设计着重在实现的速度,由于它并没有对数据做任何分析,所以并不一定是最好的算法(参考LZMA,LZ77)。

编码依据是先将资料的个别单一字符先创建成一个字符串编码表(CSET),再分别给予编号,例如原始资料为aabcaac,其字符串编码表为:

在随后的编(解)码过程,字符串编码表会随着字符串键入而逐渐扩大,如下:

因此aabcaac压缩后为112343。

解码依据是将压缩资料与原先字符串编码表对照,并将对应的字符放于一个暂存队列中,依序将压缩资料读入,若为重复资料保存于队列中,若不为重复资料,则扩展一个新的码置于字符串编码表中。例如压缩资料112343,其字符串编码表为:

步骤1:读取“1”,查字符串编码表为“a”,则:

队列Q:

输出:

步骤2:接着,再读取下一笔资料“1”,查字符串编码表为“a”,则:

队列Q:

输出:

因为aa在字符串编码表内没有,因此扩展字符串编码表为:

步骤3:此时将队列Q(1)丢弃,将Q(2)移至Q(1)位置,读取下一个资料“2”,则:

队列Q:

输出:

依上述步骤重复运作,最后可将压缩资料112343还原成原始资料aabcaac。

方法的主要关键是,它会在将要压缩的文本中,自动地创建一个先前见过字符串的字典。这些字典并不需要与这些压缩的文本一起被传输,因为如果正确地编码,解压缩器也能够依照压缩器一样的方法把它建出来,将会有完全与压缩器字典在文本的同一点有同样之字符串。

字典会从256个条目开始,每一个是给每种可能的字符(单一比特字符串)。每一次一个字符串在字典中并被见过,那么文字中,附加在单一字符后,接着该字符串的一个较长文字,就会被存储到字典中。

输出是包含字典的整数索引。这些一开始每个是9比特,当字典成长时候,可以最大增加到16位。一个特别的符号,保留来"清空字典",会把字典恢复到原先的256个条目,和9比特的索引。这对于压缩文字中含有变动字符很有用处,因为在初期的资料在文字后部分并不会有太多用处。

可变动地增加索引大小的使用是Welch贡献之一。其他是用来详细说明存储字典的一种有效率数据结构。

一般而言,字典基础的压缩会以标记(token)来取代词组(phrase)。如果标记得比特数量是少于词组所需的比特数目,那么压缩就如此产生。未压缩的文本为:

压缩过的文本:

这与有效实用上还很遥远,但是它透过词组取代举例说明了压缩方法。

这个方法在程序"压缩"上变为广泛地被使用,大约在1986年或多或少变成Unix系统中的标准工具(自很多法律和技术的原因消失之后)。数种其他受欢迎的压缩工具也使用这种方法,或者是有紧密关系的方法。

于1987年,在它变为GIF影像格式的一部分后,它变成非常广泛地被使用。它也可以(可选择)被使用于TIFF文件。

在大部分的应用中,LZW压缩算法和当时已有且广为人知的方法相比,能够提供一个比较好的压缩率。lzw压缩算法是使用在电脑上的,第一个被广泛用于一般资料的压缩,对于大的英文文本,一般可以使用lzw将其压缩到大约原来大小的一半。另外,对于其他的种类资料的压缩,它在很多情况下也相当有用。

对于LZW和类似的算法,在美国和其他国家已经发行数个专利。LZ78是包含在美国专利第4,464,650号,由兰波、立夫、柯亨(Cohn)和伊士曼(Eastman)指派给史佩瑞(Sperry)公司,后来是优利系统公司,申请于1981年8月10日,而且现在已经到期。

针对LZW算法有两个美国专利:由维克特·S·米勒(Victor S. Miller)和马克·N·维格曼(Mark N. Wegman)的美国专利第4,814,746号,指派给IBM,原本于1983年6月1日申请和卫曲的美国专利第4,558,302号,让受给史佩瑞公司,后来为优利系统公司,于1983年6月20日申请。

美国专利4,558,302是最常导致争论的一个。优利系统在当时授权免除使用费的专利执照给自由软件和免费获得的私有软件之开发者;该公司于1999年八月终止该执照。很多法律的专家已断定该专利并不包含只能解压缩LZW资料而无法压缩它的各种设备;因为这个原因,普遍使用的Gzip程序只能读取.Z档但是不能写入。

Debian每周新闻以comp.compression讨论串为基础所作的报导,称在美国的优利系统专利于它被授权后的17年又10天之后的2002年12月20日到期。大部分其他来源宣称该专利于它提出申请的20年后的2003年6月到期。

根据优利系统网站上的一个陈述,在英国、法国、德国、意大利、和日本之LZW相对应的专利,已经在2004年6月过期,而加拿大的专利于2004年7月7日到期。

IBM的美国专利已于2006年8月11日到期。

虽然LZW缩写明显地是意指Lempel、Ziv、和Welch这些发明者,某些人声称知识产权是给Ziv为第一位,因此这个方法必须称为,而不是。

相关

  • 听力听觉指声源的振动所引起的声波,通过外耳和中耳组成的传音系统传递到内耳,经内耳的环能作用将声波的机械能转变为听觉神经上的神经冲动,后者传送到大脑皮层听觉中枢而产生的主观
  • 中石化安顺厂污染案坐标:23°1′49.16″N 120°7′24.32″E / 23.0303222°N 120.1234222°E / 23.0303222; 120.1234222 台湾中石化安顺厂污染案,又称为台碱安顺厂污染案,是一件发生于台湾台南市
  • 甲磺隆甲磺隆(英语:Metsulfuron-methyl)是一种磺酰脲类除草剂,用于除去阔叶杂草和一些一年生野草。甲磺隆是一种人工合成的有机化合物,具有叶片和土壤活性,能抑制嫩芽和根尖的细胞分裂。
  • 李季谷李季谷(1895年-1968年),原名宗武,浙江绍兴人,华东师范大学历史系教授,国立台湾师范大学首任校长。1917年毕业于浙江省立第一师范学校。1920年赴日本留学,在东京高等师范学校学习外国
  • 奈特氏不确定性在经济学,奈特氏不确定性(英语:Knightian uncertainty),指无法被衡量期望值、不能被计算或然率、无法被预知的风险。由经济学家法兰克·奈特提出。在他的成名作《风险、不确定性
  • 优洛县 (加利福尼亚州)优洛县(英语:Yolo County)是美国加州中北部的一县,毗邻萨克拉门托县、索拉诺县、纳帕县、湖县、科卢萨县、和萨特县等加州县份。县首府位于伍德兰市(Woodland)。根据2000年人口普
  • 马哈赞巴河马哈赞巴河(马达加斯加语:Mahajamba),是马达加斯加的河流,位于该国北部,由索非亚区负责管辖,流经安卡拉凡兹卡国家公园,河道全长298公里,流域面积14,883平方公里。
  • 曹虎曹虎(430年代-499年)《南史》作曹武,中国刘宋、南齐时代军人、政治人物,字士威,下邳郡(今江苏省睢宁县)人。本名虎头,齐武帝为他改名曹虎。宋明帝时随萧道成平定桂阳王刘休范的谋反,以
  • 兰州市长城列表兰州市长城列表列出中国甘肃省兰州市的古代长城墙体及附属设施。
  • 埃里克·戴尔埃里克·戴尔(英语:Eric Dier,1994年1月15日-),英格兰足球运动员,现效力英格兰足球超级联赛俱乐部热刺。他是一位后场多面手,不论中后卫、右后卫、后腰都可胜任。最后更新:2021年5月19日最后更新:2020年11月18日