Huffman压缩原理

《Huffman压缩原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Huffman压缩原理科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方法，可以降低这种冗余度。贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。D.A.Huffman于1952年第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。从此，数据压缩开始在商业程序中实现并被应

2、用在许多技术领域。到1977年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们一直在绞尽脑汁为使用Huffman编码的程序找出更快、更好的改进方法。1977年，以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(CompressionofIndividualSeque

3、ncesviaVariable-RateCoding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从Shannon到Huffman到算术压缩的传统思路。因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩

4、程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，ZIP格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。Huffman压缩原理科学家在研究中发现，大多数信息的表达都存在着一定的冗余度，通过采用一定的模型和编码方

5、法，可以降低这种冗余度。贝尔实验室的ClaudeShannon和MIT的R.M.Fano几乎同时提出了最早的对符号进行有效编码从而实现数据压缩的Shannon-Fano编码方法。D.A.Huffman于1952年第一次发表了他的论文“最小冗余度代码的构造方法”(AMethodfortheConstructionofMinimumRedundancyCodes)。从此，数据压缩开始在商业程序中实现并被应用在许多技术领域。到1977年，数据压缩的研究工作主要集中于熵、字符和单词频率以及统计模型等方面，研究者们

6、一直在绞尽脑汁为使用Huffman编码的程序找出更快、更好的改进方法。1977年，以色列人JacobZiv和AbrahamLempel发表了论文“顺序数据压缩的一个通用算法”(AUniversalAlogrithemforSequentialDataCompression)。1978年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(CompressionofIndividualSequencesviaVariable-RateCoding)。所有的一切都改变了，在这两篇论文中提出的两个压缩技

7、术被称为LZ77和LZ78(不知为什么，作者名字的首字母被倒置了)。简单地说，这两种压缩方法的思路完全不同于从Shannon到Huffman到算术压缩的传统思路。因此，人们将基于这一思路的编码方法称作“字典”式编码。字典式编码不但在压缩效果上大大超过了Huffman，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。80年代中期以后，人们对LZ77进行了改进，随之诞生了一批我们今天还在大量使用的压缩程序。HaruyasuYoshizaki(Yoshi)的LHarc和RobertJung的ARJ是其中两个

8、著名的例子。LZ77得以和LZ78、LZW一起垄断当今的通用数据压缩领域。目前，基于字典方式的压缩已经有了一个被广泛认可的标准，从古老的PKZip到现在的WinZip，特别是随着Internet上文件传输的流行，ZIP格式成为了事实上的标准，没有哪一种通用的文件压缩、归档系统敢于不支持ZIP格式。 ht首先被提出来，是为了解决这样的问题：    对于N种数据（比如5种数据：A、B、C、D、E），在出现的频率已知的情况下（比如分