下载文档原格式
算术编码+ 统计模型= 数据压缩- 第一部分：算术编码作者：Mark Nelson现在通用的大多数数据压缩方法都属于两大阵营之一：基于字典的方案和统计方法。
在小系统世界中，基于字典的数据压缩技术此时似乎更加流行。
不过，通过将算术编码与强大的模型技术结合在一起，数据压缩的统计方法可以真正达到更好的性能。
这篇分成两部分的文章讨论了如何用几个不同的模型方法与算术编码组合以达到一些重大的压缩率。
本文的第一部分详细说明算术编码是如何工作的。
第二部分说明如何开发一些可以使用算术编码的有效模型以生成高性能压缩程序。
钟爱的术语数据压缩通常通过从输入“文本”获取“符号”、处理它们，并将“代码”写入到压缩后的文件来进行运作。
对于本文来说，符号通常是字节，但是他们很可能只是像素、80 位的浮点数或者EBCDIC 字符。
数据压缩方案需要能够将已压缩的文件转换回到与输入文本的一样的拷贝才是有效的。
如果已压缩的文件比输入文本更小，那么不必说，它也是有用的。
基于字典的压缩系统通过用固定长度码来代替输入文本中的一组符号来进行运作。
字典技术的一个众所周知的例子是LZW 数据压缩。
（请参见DDJ 的89 年第10 期中的“LZW 数据压缩”一文）。
LZW 通过通常从9 到16 位大小范围的码来取代本来无限长的字符串来进行运作。
数据压缩的统计方法采取一种完全不同的方法。
它们通过一次编码多个符号来运作。
将符号编码到可变长的输出码中。
输出码的长度根据符号的概率或者频率进行变化。
低概率的符号用较多的位进行编码，并且高概率符号用较少的位进行编码。
实践中，统计和字典方法之间的分界线并不总是那么清晰。
一些方案并不能明显地归为某一个阵营或者另一个，并且总是有一些使用来自两种技术特性的混合方案。
不过，在本文中讨论的方法使用算术编码来实现纯粹的统计压缩方案。
霍夫曼（Huffman）编码：退役的冠军在数据流中只是能够精确地计算字符的概率还不够，我们也需要能有效地利用这个知识的编码方法。
费诺编码课程设计一、课程目标知识目标：1. 理解费诺编码的基本原理和数学背景；2. 掌握费诺编码的算法步骤，能够运用编码方法进行简单信息编码；3. 了解费诺编码在实际通信系统中的应用及其优势。
技能目标：1. 能够运用费诺编码对文字、图像等不同类型的信息进行编码；2. 培养学生的逻辑思维能力和问题解决能力，通过团队合作完成费诺编码的实际操作；3. 提高学生的信息处理能力，学会在信息传输过程中优化编码，提高通信效率。
情感态度价值观目标：1. 培养学生对信息科学的兴趣，激发他们探索通信领域奥秘的热情；2. 引导学生认识信息编码在国家安全、科技进步和社会发展中的重要作用，增强他们的责任感和使命感；3. 培养学生的团队协作精神，使他们学会在合作中解决问题，共同成长。
课程性质：本课程为信息技术与通信原理相结合的实践课程，旨在帮助学生掌握费诺编码的理论知识，培养实际操作能力。
学生特点：六年级学生具备一定的数学基础和逻辑思维能力，对新鲜事物充满好奇心，善于合作与交流。
教学要求：结合学生特点，注重理论与实践相结合，通过任务驱动、分组合作等教学策略，提高学生的学习兴趣和实际操作能力。
在教学过程中，关注学生的个体差异，引导他们主动探究、积极思考，培养解决问题的能力。
将课程目标分解为具体的学习成果，以便在教学设计和评估中达到预期效果。
二、教学内容1. 费诺编码原理：- 线性代数基础知识：向量空间、线性变换；- 编码理论基本概念：编码、解码、错误纠正；- 费诺编码基本原理：费诺不等式、最小距离、编码效率。
2. 费诺编码算法：- 编码算法步骤：生成矩阵、编码过程；- 解码算法步骤：伴随矩阵、纠错能力；- 实例分析：具体案例展示费诺编码的编码与解码过程。
3. 费诺编码应用：- 数字通信系统中的应用：提高通信效率、降低误码率；- 现实生活中的应用案例：光纤通信、卫星通信等；- 编码优化：针对不同场景选择合适的编码方案。
4. 实践操作：- 软件工具使用：介绍相关软件工具，如Matlab等；- 编码与解码实践：分组进行费诺编码的实际操作，包括编码、解码及性能分析；- 团队协作：分组完成任务，培养学生的合作精神和沟通能力。
实验一信息熵与图像熵计算（2 学时）一、实验目的1.复习MATLAB的基本命令，熟悉MATLAB下的基本函数；2.复习信息熵基本定义,能够自学图像熵定义和基本概念。
二、实验内容1.能够写出MATLAB源代码，求信源的信息熵；2.根据图像熵基本知识，综合设计出MATLAB程序，求出给定图像的图像熵。
三、实验仪器、设备1.计算机－系统最低配置256M内存、P4 CPU；2.MATLAB编程软件。
四实验流程图五实验数据及结果分析四、实验原理1.MATLAB中数据类型、矩阵运算、图像文件输入与输出知识复习。
2.利用信息论中信息熵概念，求出任意一个离散信源的熵（平均自信息量）。
自信息是一个随机变量,它是指某一信源发出某一消息所含有的信息量。
所发出的消息不同，它们所含有的信息量也就不同。
任何一个消息的自信息量都代表不了信源所包含的平均自信息量。
不能作为整个信源的信息测度，因此定义自信息量的数学期望为信源的平均自信息量：1( ) 1 ( ) [log ] ( ) log ( ) i n i i p a i H E p a p a X 信息熵的意义：信源的信息熵H是从整个信源的统计特性来考虑的。
它是从平均意义上来表征信源的总体特性的。
对于某特定的信源，其信息熵只有一个。
不同的信源因统计特性不同，其熵也不同。
3.学习图像熵基本概念，能够求出图像一维熵和二维熵。
图像熵是一种特征的统计形式，它反映了图像中平均信息量的多少。
图像的一维熵表示图像中灰度分布的聚集特征所包含的信息量，令Pi表示图像中灰度值为i的像素所占的比例，则定义灰度图像的一元灰度熵为：2550 log i i i p p H图像的一维熵可以表示图像灰度分布的聚集特征，却不能反映图像灰度分布的空间特征，为了表征这种空间特征，可以在一维熵的基础上引入能够反映灰度分布空间特征的特征量来组成图像的二维熵。
选择图像的邻域灰度均值作为灰度2分布的空间特征量，与图像的像素灰度组成特征二元组，记为(i,j)，其中i表示像素的灰度值(0<=i<=255)，j表示邻域灰度(0<=j<=255),2 ( , ) / ij p f i j N上式能反应某像素位置上的灰度值与其周围像素灰度分布的综合特征，其中f(i,j)为特征二元组(i,j)出现的频数，N为图像的尺度，定义离散的图像二维熵为:2550 log ij ij i p p H构造的图像二维熵可以在图像所包含信息量的前提下，突出反映图像中像素位置的灰度信息和像素邻域内灰度分布的综合特征。
自适应算术编码的原理实现与应用简介自适应算术编码（Adaptive Arithmetic Coding）是一种无损数据压缩算法，用于将输入数据流转换为更短的编码表示形式。
相对于固定长度编码，自适应算术编码能够更好地利用数据的统计特性，从而达到更高的压缩比。
本文将介绍自适应算术编码的原理实现与应用，并对其进行详细的解释与示例。
原理自适应算术编码的原理非常简单，主要分为以下几个步骤：1.定义符号表：首先，需要将输入数据中的符号进行编码，因此需要定义一个符号表，其中包含了所有可能的符号及其概率。
符号可以是字符、像素、或者任意其他离散的数据单元。
2.计算累积概率：根据符号表中每个符号的概率，计算出累积概率。
累积概率用于将输入数据中的符号映射到一个区间上。
3.区间编码：将输入数据中的符号通过区间编码进行压缩。
每个符号对应一个区间，区间的大小与符号的概率成比例。
4.更新概率模型：在每次编码过程中，根据已经编码的符号，可以得到新的概率模型。
根据这个模型，可以动态地调整符号表中每个符号的概率。
这样，在下一次编码中，就能更好地适应数据的统计特性。
实现步骤与示例1.定义符号表假设我们要对一个字符串进行压缩，其中包含的符号为’a’、’b’、’c’、’d’和’e’。
我们可以根据经验或者统计数据，估计每个符号的概率。
例如：’a’的概率为0.2，’b’的概率为0.15，’c’的概率为0.3，’d’的概率为0.25，’e’的概率为0.1。
2.计算累积概率根据符号表中每个符号的概率，计算出累积概率。
累积概率可以通过累计每个符号的概率得到。
在本示例中，累积概率为：’a’的概率为0.2，’b’的概率为0.35，’c’的概率为0.65，’d’的概率为0.9，’e’的概率为1.0。
3.区间编码使用累积概率对输入数据中的符号进行区间编码。
假设我们要对字符串’abecd’进行编码。
–第一个符号为’a’，其累积概率为0.2。
因此，我们将区间[0,1.0)划分为5个小区间，每个小区间对应一个符号：•’a’对应的区间为[0,0.2)；•’b’对应的区间为[0.2,0.35)；•’c’对应的区间为[0.35,0.65)；•’d’对应的区间为[0.65,0.9)；•’e’对应的区间为[0.9,1.0)。
课程设计目录一、概述1、设计目的2、设计任务3 、所用软件环境二、需求分析1、问题描述2、基本要求三、设计过程1、霍夫曼编码2、费诺编码3、游程编码4、算术编码一、概述1设计目的1.1深刻理解信源编码的基本思想与目的；1.2深刻理解并掌握霍夫曼编码译码、费诺编码译码、游程编码译码、算术编码译码的原理与方法；1.3提高综合利用所学理论知识独立分析和解决问题的能力，提高编程能力。
2设计任务2.1对任意的字符分别进行2元霍夫曼编码、2元费诺编码、游程编码和算术编码，并进行相应的译码；2.2注意编码效率的计算.3 所用软件环境Visual C++ 6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。
Visual C++是一个功能强大的可视化软件开发工具。
自1993年Microsoft公司推出Visual C++1.0后，随着其新版本的不断问世，Visual C++已成为专业程序员进行软件开发的首选工具。
Visual C++6.0由Microsoft开发, 它不仅是一个C++ 编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。
Visual C++6.0由许多组件组成，包括编辑器调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。
这些组件通过一个名为Developer Studio的组件集成为和谐的开发环境Microsoft的主力软件产品。
Visual C++是一个功能强大的可视化软件开发工具。
二、需求分析1问题描述1.1霍夫曼编码首先要解决的问题是给定一段字符串，如何建造霍夫曼树；怎样根据该树求每个字符的编码，并对该段字符串进行编码；怎么样将得到的编码进行译码；怎么样遍历输出树中的叶子节点。
1.2费诺编码,给定一段字符串，如何排序；分治法编码如何实现；如何计算频率并求编码效率。
费诺编码原理费诺编码费诺编码（Huffman Coding）是一种常用的可变长度编码方式，旨在实现对信息的高效压缩。
本文将从浅入深，逐步解释费诺编码的原理和应用。
1. 简介费诺编码由美国数学家大卫·费诺（David A. Huffman）于1952年提出，它基于信息中出现的字符频率进行编码。
通过将出现频率较高的字符使用较短的编码，而出现频率较低的字符使用较长的编码，费诺编码实现了压缩效果。
2. 编码原理费诺编码的实现过程如下：•统计待编码文本中每个字符的出现频率。
•根据字符频率构建费诺树（Huffman Tree），频率越高的字符位于树的顶部，频率越低的字符位于树的底部。
•为每个字符赋予编码，频率更高的字符使用较短的编码，频率更低的字符使用较长的编码。
•将编码应用于待编码文本，将其转换为费诺编码形式。
3. 示例说明以下是一个简单的示例，用于说明费诺编码的工作原理。
考虑待编码文本中的字符及其出现频率如下：字符频率A 5B 1C 2D 3按照费诺编码的原则，我们可以构建出如下的费诺树：Root/ \11 7/ \4 3/ \ / \A 1 C D|B根据费诺树，我们为每个字符分配编码：字符频率编码A 5 0B 1 110C 2 10D 3 111将待编码文本“AABACDCD” 转换为费诺编码形式：AABACDCD =>可以看到，使用费诺编码后，原文本被高效地压缩。
4. 应用场景费诺编码在很多领域都有广泛应用，尤其在数据压缩和信息存储中起到重要作用。
例如，压缩文件、图像、音频和视频文件时，常常使用费诺编码。
由于费诺编码可根据数据的特征自适应地调整编码长度，因此能够实现较高的压缩比。
5. 总结费诺编码是一种高效的可变长度编码方式，通过频率统计和构建费诺树，将出现频率较高的字符使用较短的编码，从而实现信息的高效压缩。
费诺编码在数据压缩和信息存储领域有着广泛应用。
希望本文对费诺编码的原理和应用有所帮助，欢迎阅读与讨论！。
信息论与编码第二版答案《信息论与编码（第二版）》是Claude Elwood Shannon所撰写的经典著作，该书于1948年首次出版，至今被广泛认可为信息论领域的权威指南。
本书通过数学模型和理论阐述了信息的量化、传输、存储以及编码等相关概念和原理。
深入浅出的阐述方式使得本书具备了普适性和可读性，成为信息论领域学习者和研究者的必备参考。
信息论是研究信息的传输、处理和应用的科学，其最初来源于通信工程领域。
而编码作为信息论的一个重要分支，旨在寻求一种有效的方式将信息转化为符号或信号，以便能够高效地传输和存储。
编码的主要目标是通过减少冗余或利用统计特征来压缩信息，并提高信号传输过程中的容错性。
在信息论中，最重要的概念之一是“信息熵”。
信息熵是信息的不确定性度量，也可以看作是信息的平均编码长度。
当一个事件出现的可能性均匀时，信息熵达到最大值，表示信息的不确定度最高；而当事件的概率趋于一个时，信息熵达到最小值，表示事件的确定性最高。
例如，抛一枚公正的硬币，其正反面出现的概率均为0.5，那么信息熵将达到最大值，即1比特。
如果硬币是正面朝上或者反面朝上，那么信息熵将达到最小值，即0比特。
除了信息熵，信息论中还有许多重要的概念，如条件熵、相对熵和互信息等。
其中，条件熵表示给定某些信息后的不确定性，相对熵则用于比较两个概率分布之间的差异，而互信息则度量了两个随机变量之间的相关性。
编码是信息论中的关键技术之一，其目的是将信息通过某种规则进行转换，使其适于传输或存储。
常见的编码方法有哈夫曼编码、香农-费诺编码和算术编码等。
其中，哈夫曼编码常用于无损压缩，通过根据字符频率设计不等长的编码，使得频率高的字符用较短的编码表示，而频率低的字符用较长的编码表示，从而达到压缩的效果。
算术编码则通过将整个信息序列映射为一个实数，从而实现更高的压缩比。
信息论与编码的研究对众多领域都具有重要意义。
在通信领域中，信息论的结果对于提高信道容量和降低误差率具有指导意义。
吉林建筑大学电气与电子信息工程学院信息理论与编码课程设计报告设计题目：费诺编码专业班级学生姓名：学号：指导教师：设计时间：2014.11.24－2014.12.5第1章 概述1.1设计的作用、目的《信息论与编码》是一门理论与实践密切结合的课程,课程设计是其实践性教学环节之一，同时也是对课堂所学理论知识的巩固和补充。
其主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。
通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。
1.2设计任务及要求1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2．根据费诺编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到费诺编码；3．掌握费诺编码的优缺点；4．能够使用MATLAB 或其他语言进行编程，编写的函数要有通用性，要理解每个函数的具体意义和适用范围，对主要函数的功能和参数做详细说明。
1.3设计内容费诺编码属于概率匹配编码，但不是最佳的编码方法。
在编N 进制码时首先将信源消息符号按其出现的概率依次由小到大排列开来，并将排列好的信源符号按概率值分N 大组，使N 组的概率之和近似相同，并对各组赋予一个N 进制码元0、1……N-1。
之后再针对每一大组内的信源符号做如上的处理，即再分为概率和相同的N 组，赋予N 进制码元。
如此重复，直至每组只剩下一个信源符号为止。
此时每个信源符号所对应的码字即为费诺码。
针对同一信源，费诺码要比香农码的平均码长小，消息传输速率大，编码效率高。
一个有8个符号的信源X ，各个符号出现的概率为：进行费诺编码，并计算平均码长、编码效率、冗余度。
XP （X ）X1, X2, X3, X4, X5, X6, X7, X8 0.19, 0.18, 0.17, 0.16, 0.13, 0.10, 0.06, 0.01第2章费诺编码2.1设计原理1.编码与信源编码在学过信息论与编码以后，对这方面内容已有了基础的了解。
课程设计---费诺编码和自适应算术编码信息论课程设计信息论课程设计课题名称:四元费诺编码自适应算术编码专业班级:任课教师:姓名:学号:完成时间:2012-12合肥工业大学计算机与信息学院第 1 页信息论课程设计四元费诺编码1.问题描述费诺编码方法属于概率匹配编码。
这种编码方法不是最佳的编码方法，但有时也可得到最佳码的性能。
设计一个程序对输入的一个字符串实现费诺编码。
2.基本要求书本上大多讲解的二元的费诺编码，但是多元的费诺编码也能实现。
请设计程序用以对输入字符串实现4元费诺编码，并且设计译码函数使满足根据编码的结果，输入任意的4进制数字串能够正确唯一的译码，最后计算编码效率。
3.二元费诺编码基本原理首先,将信源符号以概率递减的次序排列进来，将排列好的信源符号划分为两大组，使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后，将每一大组的信源符号再分成两组，使同一组的两个小组的概率和近于相同，并又分别赋予一个二元码符号。
依次下去，直至每一个小组只剩下一个信源符号为止。
这样，信源符号所对应的码符号序列则为编得的码字。
译码原理，按照编码的二叉树从树根开始，按译码序列进行逐个的向其叶子结点走，直到找到相应的信源符号为止。
之后再把指示标记回调到树根，按照同样的方式进行下一序列的译码到序列结束。
如果整个译码序列能够完整的译出则返回成功，否则则返回译码失败。
编码方法:1.将信源消息符号按其出现的概率大小依次排列。
2.将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。
3.将每一大组的信源符号再分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。
4.如此重复，直至每个组只剩下一个信源符号为止。
5.信源符号所对应的码字即为费诺码。
4.费诺编码特点费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率达，合肥工业大学计算机与信息学院第 2 页信息论课程设计编码效率高，但它属于概率匹配编码它不是最佳的编码方法。
5.二元费诺编码思想费诺编码最困难的是根据信源概率对信源进行分组，本次借鉴了《信息编码与加密实践》(夏娜蒋建国丁志忠编著)中的二元费诺编码的思想，设定一个中间判断值—‘old’为每次分组总概率的一半大小，‘sum’为每次相加的概率和，每次相加后与该段的中间值差得绝对值与‘old’比较，小于其值则分为一组，大于其值则为另一组。
递归调用这段程序，直到每个分组只含一个信源结束。
6.四元费诺编码流程图开始输入字符窜统计各个字符出现的频率按字符出现的概率大小对符号进行排列调用编码对函数进行编码N 字符都已编码完,Y输出编码结果输入要编码的数字串合肥工业大学计算机与信息学院第 3 页信息论课程设计调用译码函数译码输出编码结果结束7.四元费诺编码思想与函数模块划分四元费诺编码主要在二元费诺编码的基础上修改编码函数，即二元费诺编码每次递归分两组，四元费诺编码每次就要分为四组。
具体修改方法如下: ,参数说明合肥工业大学计算机与信息学院第 4 页信息论课程设计,递归结束条条件,递归函数合肥工业大学计算机与信息学院第 5 页信息论课程设计,递归分组合肥工业大学计算机与信息学院第 6 页信息论课程设计8.程序测试与结果9.总结费诺编码:由实验结果可得，在一般情况下，费诺编码不一定能使短码得到充分利用，尤其当信源符号较多，并有一些符号概率分布很接近时，分两大组的组合就会很多，可能某种分大组的结果，会出现后面小组的概率和相差较远，因而使平均码长增加。
所以，费诺码通常不是最佳码。
程序:由于时间比较仓促，无法对程序进行美化和进一步的编写窗口化程序，界面比较传统和简陋。
合肥工业大学计算机与信息学院第 7 页信息论课程设计自适应算术编码1.问题描述是图像压缩的主要算法之一。
是一种无损数据压缩方法，也是一种熵编码的方法。
和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足(0.0?n<1.0)的小数n。
2.基本要求请设计程序用以对输入字符串实现自适应的算术编码，其中要有相应的概率调整的过程，并且设计译码函数使满足根据编码的结果，能够正确的译码。
3.算术编码原理在给定符号集和符号概率的情况下，算术编码可以给出接近最优的编码结果。
使用算术编码的压缩算法通常先要对输入符号的概率进行估计，然后再编码。
这个估计越准，编码结果就越接近最优的结果。
例: 对一个简单的信号源进行观察，得到的统计模型如下:60% 的机会出现符号中性20% 的机会出现符号阳性10% 的机会出现符号阴性10% 的机会出现符号数据结束符.中性对应的区间是 [0, 0.6)阳性对应的区间是 [0.6, 0.8)阴性对应的区间是 [0.8, 0.9)数据结束符对应的区间是 [0.9, 1)当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。
任何人使用该区间和使用的模型参数即可以解码重建得到该符号序列。
实际上我们并不需要传输最后的结果区间，实际上，我们只需要传输该区间中的一个小数即可。
在实用中，只要传输足够的该小数足够的位数(不论几进制)，以保证以这些位数开头的所有小数都位于结果区间就可以了。
4.自适应算术编码合肥工业大学计算机与信息学院第 8 页信息论课程设计自适应算术编码即上述的模型还可以进行自适应的变化，即在某种上下文下出现的概率分布的估计随着每次这种上下文出现时的符号而自适应更新，从而更加符合实际的概率分布。
不管编码器使用怎样的模型，解码器也必须使用同样的模型。
编码过程的每一步，除了最后一步，都是相同的。
编码器通常需要考虑下面三种数据:1.下一个要编码的符。
2.当前的区间(在编第一个符号之前，这个区间是[0,1), 但是之后每次编码区间都会变化3.编码其将当前的区间分成若干子区间，每个子区间的长度与当前上下文下可能出现的对应符号的概率成正比。
当前要编码的符号对应的子区间成为在下一步编码中的初始区间。
5.自适应算术编码特点1)不必预先定义概率模型,自适应模式具有独特的优点;2)信源符号概率接近时,建议使用算术编码,这种情况下其效率高于Huffman编码;3)算术编码绕过了用一个特定的代码替代一个输入符号的想法,用一个浮点输出数值代替一个流的输入符号,较长的复杂的消息输出的数值中就需要更多的位数。
4)算术编码实现方法复杂一些,但JPEG成员对多幅图像的测试结果表明,算术编码比Huffman编码提高了5%左右的效率,因此在PEG扩展系统中用算术编码取代Huffman编码。
6.自适应算法流程图开始初始化概率空间和准备数据合肥工业大学计算机与信息学院第 9 页信息论课程设计输入字符串字符找到相应的概率空间调整字符概率序列调整指针指向下一字符N字符都已编码,Y区间内任选一树转二进制并去相应的有效位输出编码结果结束7.自适应算术编码编程思想算法主要基于算术编码，其中编码译码都要增加一个概率调整的式子。
编程思想如下:合肥工业大学计算机与信息学院第 10 页信息论课程设计(1)对一组信源符号按照符号的概率排序，将[0,1)设为当前分析区间。
按信源符号的概率序列在当前分析区间划分比例间隔。
(2)检索“输入消息序列”，锁定当前消息符号(初次检索的话就是第一个消息符号)。
找到当前符号在当前分析区间的比例间隔，将此间隔作为新的当前分析区间。
并把当前分析区间的起点(即左端点)指示的数“补加”到编码输出数里。
当前消息符号指针后移。
(3)根据输如的字符，相应的调整信源的概率序列。
(4)按照新的信源符号的概率序列在当前分析区间划分比例间隔。
然后重复第二步。
直到“输入消息序列”检索完毕为止。
(5)最后的编码输出数就是编码好的数据。
修改信源概率序列方法:Cnt[i] 为相应信源符号的出现次数，初始化都为1;Sum 为总共的信源符号Proc[i] 为相应信源符号的概率areaBegin 为区间起始概率areaEnd 为区间结束概率合肥工业大学计算机与信息学院第 11 页信息论课程设计8.程序测试与结果9.总结自适应算术编码:不必预先定义概率模型,自适应模式具有独特的优点，没有对个输入符号的信息量为整数的限制，随着编码结果的小数随位数的增加，它的精度也随之增高，从信息的角度来说，它所含的信息量也随之增加。
信源符号概率接近时编码效率比较好，其效率高于哈夫曼编码。
程序:自己在指导书的程序基础上修改了编码译码函数，总体来说还是比较轻松简单的。
但是因为时间比较紧，没有足够的时间对程序进行可视化窗口编程和美化，所以程序基于黑白对话框比较简陋;输入字符要手动输入，过程比较繁琐，容易出错，可以在以后增加文件操作和成熟美化等工作，使程序简单实用。
合肥工业大学计算机与信息学院第 12 页信息论课程设计附录一:费诺编码源程序// Fano编括?码?.cpp : 定?义?控?制??应畖用?程ì序ò的?入?口ú点?。
, //// Fano编码.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h" #include<stdio.h>#include<math.h>#include<string.h> #include<algorithm>using namespace std; typedef struct{char data;float weight;char code[1000];}fnode;fnode f[50];int num;int forwd,mid,last; int jsq(char*s,int cnt[],char str[]) {char *p;int i,j,k=0;int temp[257];for(i=0;i<257;i++)temp[i]=0;for(p=s;*p!='\0';p++)temp[*p]++;for(i=0,j=0;i<=256;i++)if(temp[i]!=0){j++;str[j]=i;cnt[j]=temp[i];}return j;}//shuruvoid Input(char receive[],int cnt[],char str[]){unsigned int len=0;合肥工业大学计算机与信息学院第 13 页信息论课程设计printf("输入要编码的字符串:");gets(receive);len=strlen(receive);num=jsq(receive,cnt,str);for(int i=1;i<=num;i++){f[i-1].data=str[i];f[i-1].weight=float(cnt[i])/len;}}//编码void code(fnode f[],double total,int begin,int end){//double sum=0.0,tsum=0.0,temp1old=total/2;doublesum=0.0,fsum=0.0,msum=0.0,lsum=0.0,temp1=0.0,temp2=0.0,temp3=0.0,old 1=total/4,old2=total/4,old3=total/4;//int forwd,mid,last;if(end-begin==0)return;elseif (end-begin==1){strcat(f[begin].code,"0"); strcat(f[begin+1].code,"1"); return;}elseif (end-begin==2){strcat(f[begin].code,"0"); strcat(f[begin+1].code,"1"); strcat(f[begin+2].code,"2"); return;}elseif(end-begin==3){strcat(f[begin].code,"0"); strcat(f[begin+1].code,"1"); strcat(f[begin+2].code,"2"); strcat(f[begin+3].code,"3"); return;合肥工业大学计算机与信息学院第 14 页信息论课程设计}elsefor(int i=begin;i<=end;i++) {sum+=f[i].weight;temp1=fabs(sum-total/4);if(temp1<=old1){forwd=i;fsum=sum;strcat(f[i].code,"0");old1=temp1;}else{//temp=fabs(sum)//msum=sum-fsum;temp2=fabs(sum-fsum-total/4); if (temp2<=old2){mid=i;msum=sum-fsum;strcat(f[i].code,"1");old2=temp2;}else{temp3=fabs(sum-fsum-msum-total/4); if(temp3<=old3){last=i;lsum=sum-fsum-msum;strcat(f[i].code,"2");old3=temp3;}elsestrcat(f[i].code,"3");}}//old3=temp3;}code(f,fsum,begin,forwd);code(f,msum,forwd+1,mid);合肥工业大学计算机与信息学院第 15 页信息论课程设计code(f,lsum,mid+1,last);code(f,sum-fsum-msum-lsum,last+1,end); }//译码void decode(char s[]) {unsigned int i=0;int j=0;char s2[100];s2[0]='\0';while(i< strlen(s)){char temp[2];temp[0]=s[i];temp[1]='\0';strcat(s2,temp);for(j=0;j<num;j++)//分别与各个编码比较{if(strcmp(s2,f[j].code)==0)//判断是否匹配{printf("%c",f[j].data);s2[0]='\0';break;}}i++;}}//输出结果void print(){int i;for(i=0;i<num;i++)//cout<<"符号"<<f[i].codeprintf("符号%c概率%f,编码为%s\n",f[i].data,f[i].weight,f[i].code); }//计算编码效率double code_ratio(fnode f[50],char receive[],int cnt [],char str[]) {double up=0.0,down=0.0,temp=0.0;int i=1,j,len=strlen(receive);for (i;i<=num;i++){合肥工业大学计算机与信息学院第 16 页信息论课程设计temp=cnt[i]/double(len);up-=temp*(log10(temp)/log10(4.0));for (j=0;j<50;j++)if(f[j].data==str[i])down+=temp*strlen(f[j].code);}return(up/down)*100;}//sort 函数的参数bool Myless(const fnode l,const fnode r){return l.weight>r.weight; }void main(){//int forwd,mid,last;char got[1000],s[1000]={'\0'},receive[1000],str[1000];//got接收输入的待解码的字符串，s接受解码的结果，receive接受输入的字符串int cnt[1000]; //str,cnt分别统计字符中的字符和其出现的概率Input(receive,cnt,str); //调用输入函数sort(f,f+num,Myless); //调用排序函数code(f,1.0,0,num-1); //调用编码函数print(); //调用输出编码函数printf("上述字符串的费诺编码为");int i=0,j=0;while (receive[i]!='\0'){for(j=0;j<num;j++)if (f[j].data==receive[i]){printf("%s",f[j].code);break;}i++;}printf("\n编码效率:%f%%\n",code_ratio(f,receive,cnt,str));printf("请输入四进制码开始的解码:\n");gets(got);strcat(s,got);printf("译码结果为:");decode(s); //调用译码函数printf("\n");//system("pause");合肥工业大学计算机与信息学院第 17 页信息论课程设计附录二:自适应算术编码 // 自适应算术编码.cpp : 定义控制台应用程序的入口点。
