发布时间 : 星期四 文章算术编码与哈夫曼编码更新完毕开始阅读
安徽大学
本科毕业论文（设计、创作）
题 目： 哈夫曼编码与算术编码压缩效率比较 学生姓名： 李伟 学号： E20714134 院（系）： 计算机科学与技术 专业： 软件工程 入学时间： 2007 年 9 月 导师姓名： 韩莉 职称/学位： 讲师/硕士 导师所在单位： 安徽大学计算机科学与技术学院 完成时间： 2011 年 5 月
哈夫曼编码与算术编码压缩效率比较
摘要
算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息 熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算 要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各 种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理 过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并 讨论了怎样把信源符号映射为对应的码字，过程中用到的哈夫曼编码表是编码与解码的关键。在第4章对两者的编码效率作了比较，主要是结合信息论中的一些概念从微观上对两者逼近信息熵的能力作了比较，并在这章最后对两者在文本文件的压缩效果的表现上给出了一些实验结果。最后，在5章，主要是对前面内容做了些补充和总结。
关键词：信息熵；算术编码；哈夫曼编码；编码效率
The comparison of Huffman Coding and Arithmetic Coding in File
Compression Abstract
Full use of the probability distribution of source symbols is the feature of the arithmetic encoding and Huffman encoding. Approaching the average code length to the information entropy come first when designing a compression algorithm. To the capacity of closing to information entropy, arithmetic encoding is stronger than Huffman encoding. However, the coding efficiency and implementation is often a contradiction: to improve coding efficiency, which means the algorithm implementation process needs to pay a higher price. Therefore, you need to weigh both when choosing a compression algorithm. In the beginning of this thesis, it first introduced some of the concepts of information theory. Because encoding algorithms are derived from information theory and information theory is the mathematical foundation of various coding algorithms. Then in Chapter 2, it introduces the principle of arithmetic coding. For better to understand the binary arithmetic coding principle, it first introduces the unlimited precision arithmetic coding. In Chapter 3, it describes the Huffman coding theory, and discusses how to map source symbol to the corresponding code word, among which Huffman coding and decoding table is the key. In Chapter 4, the coding efficiency of the two algorithms is compared. Mainly compare the capacities to approximate information entropy with some of the concepts in information theory. And the final part in this chapter, some experimental results are given to show the compression effect to compress a text file. Finally, in Chapter 5, it gives some additions and summary.
Keywords: Information Entropy; Arithmetic Coding; Huffman Coding; Coding Efficiency
目 录
1 引言??????????????????????????????1 1.1 数据压缩概念及技术分类????????????????????1 1.2 统计编码的数学准备??????????????????????2 1.3 统计编码简介?????????????????????????5 2 算术编码????????????????????????????5 2.1 算术编码简介?????????????????????????5 2.2 无限精度的算术编码??????????????????????6 2.3 二进制编码??????????????????????????9 2.4 二进制解码??????????????????????????13 3 哈夫曼编码???????????????????????????14 3.1 哈夫曼编码简介????????????????????????14 3.2 哈夫曼编码原理????????????????????????14 3.3 哈夫曼解码原理????????????????????????16 3.4 哈夫曼编码与解码系统模型???????????????????16 3.5 哈夫曼编码形式不唯一?????????????????????17 4 算术编码与哈夫曼编码的比较???????????????????17 4.1 两者编码效率的比较??????????????????????17 4.2 两者压缩率的比较???????????????????????19 5 总结??????????????????????????????20 主要参考文献???????????????????????????22 致谢???????????????????????????????23