- 1、本文档共13页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
声明
本论文题目:算术编码算法的分析与实现,作者:叶叶,于2010 年10 月16 日在编程
论坛上发表。页面地址:/bbs/view12-29356-1.htm 。本论文全文及相关
配套程序可以在上述页面中下载。请尊重他人劳动成果,转载或引用时请注明出处。
目录
1 前言2
2 理论2
2.1 编码2
2.2 解码3
3 改进4
3.1 整数运算4
3.2 正规化5
4 实现8
4.1 编码8
4.2 解码10
4.3 统计模型11
5 分析12
6 结束语12
参考文献13
附录13
算术编码算法的分析与实现
作者:叶叶(网名:yeye55 )
摘要:分析了算术编码的理论基础,着重介绍WNC 算法的实现方式。详细讨论了算术
编码原理、正规化操作、WNC 算法代码实现等技术。给出了一个切实可行的应用程序。
关键词:算术编码;正规化;Delphi
中图分类号:TP301.6
1 前言
[1]
早在1948 年C. E. Shannon 提出信息论 的时候,就提出了算术编码的思想。但是经过
多年的研究,许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算,
这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入,终于在 1987
年Ian H. Witten、Radford M. Neal 和John G. Cleary 发表了一篇论文[2],提出了一种基于整数
运算的算术编码实现算法。该算法后来被命名为CACM87,并应用于ITU-T 的H.236 视频
编码标准。也有学者根据作者姓名将该算法称之为WNC 算法。WNC 算法是一个实用性算
法,它可以应用在许多方面。在Witten 等人的论文[2] 中给出了一个使用C 语言编写的WNC
算法实现程序的源代码(以下简称“WNC 源代码”)。在许多时候,WNC 源代码已经作为
算术编码的范本程序来使用。本文将分析算术编码的理论基础,并着重介绍WNC 算法的实
现方式。同时给出一个在Delphi 7.0 下开发,使用算术编码算法压缩数据的应用程序。
2 理论
2.1 编码
算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1
同时大于0 的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的
熵值,从而获得理论上的最高压缩率。
算术编码进行编码时,从实数区间[0,1)开始。按照符号的频度将当前的区间分割成多个
子区间。根据当前输入的符号选择对应的子区间,然后从选择的子区间中继续进行下一轮的
分割。不断的进行这个过程,直到所有符号编码完毕。对于最后选择的一个子区间,输出属
于该区间的一个小数。这个小数就是所有数据的编码。现在来举个例子。假设一份数据由
“A ”、“B ”、“C ”三个符号组成。现在要编码数据“BCCB ”,编码过程如图2.1 所示。
B C C B
1.0000 0.6667 0.6667 0.6667
C : 1 / 4
C : 1 / 3
C : 2 / 5
0.5834 C : 3 / 6
0.6667
文档评论(0)