范式哈夫曼算法的分析与实现.pdfVIP

声明 本论文题目：范式哈夫曼算法的分析与实现，作者：叶叶，于2010 年10 月14 日在编 程论坛上发表。页面地址：/bbs/view12-29332-1.htm 。本论文全文及相 关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。 目录 1 前言2 2 理论基础2 2.1 哈夫曼算法2 2.2 范式哈夫曼算法6 3 计算编码位长7 4 编码9 5 解码9 5.1 正常解码9 5.2 优化解码10 6 限制编码位长11 7 码表二次压缩15 7.1 指数哥伦布编码15 7.2 范式哈夫曼二次压缩17 8 测试与分析18 9 结束语20 参考文献20 附录：项目说明20 1 程序项目20 2 MemoryBuffer.pas文件21 3 CanonicalHuffman.pas文件21 4 CanHuf_Debug.pas文件22 第 1 页 共 26 页 范式哈夫曼算法的分析与实现 作者：叶叶（网名：yeye55 ） 摘要：全面介绍了范式哈夫曼算法的理论基础和实现方式。详细讨论了编码位长计算、 限制编码位长、解码优化、码表二次压缩等实现技术。并给出了一个切实可行的应用程序。 关键词：哈夫曼；范式哈夫曼；指数哥伦布编码；Delphi 中图分类号：TP301.6 1 前言 [1] David A. Huffman 于1952 年第一次提出了哈夫曼（Huffman ）算法 ，该算法一经提出 就引起了研究人员的广泛兴趣。哈夫曼算法使用变长前缀编码来压缩数据。对于出现次数较 多的符号使用较短的编码表示，对于出现次数较少的符号使用较长的编码表示。哈夫曼算法 的性能十分优异，即使在很糟糕的情况下都可以获得不错的压缩率。但是，哈夫曼算法也有 许多缺点。例如：二叉树大量占用内存、码表过大、编解码速度过慢等等。 [2] Eugene S. Schwartz 于1964 年提出了范式哈夫曼编码（Canonical Huffman Code ）算法 。 作为哈夫曼算法的一个重要的变体，范式哈夫曼算法解决了哈夫曼算法的许多不足之处。范 式哈夫曼算法可以根据编码位长算出编码。这样输出的码表就大大的减少了，而且编解码过 程不再需要二叉树结构。在提高编解码速度的同时，内存占用也大幅减少。 目前范式哈夫曼算法已经在数据压缩领域大量的应用。本文将详细的分析范式哈夫曼算 法的理论基础和实现方式，并给出一个在Delphi 7.0 下开发，使用范式哈夫曼算法压缩数据 的应用程序。 2 理论基础 2.1 哈夫曼算法 范式哈夫曼算法是哈夫曼算法的一种变体。所以这里先对哈夫曼算法进行介绍，然后再 推导出范式哈夫曼算法。 哈夫曼算法需要扫描两遍数据。第一遍扫描计算符号在数据中出现的次数（以下简称“频 度”），然后根据符号频度构建一棵哈夫曼二叉树（以下简称“哈夫曼树”）。最后再次扫描数 据将符号按哈夫曼树进行编码。例如：一份长度为38 个符号的数据，其中一共出现8 种符 号，其频度如表2.1 所示： 符号 A B C D E F G H 频度 10 1 1 11 1 1 8 5 表2.1 符号频度