算术压缩论文++基于算术编码的数据压缩算法研究与实现

托斯卡纳

文艺复兴的最初摇篮，意大利的静谧空间…

?首页

?关于

?珞樱

?推荐

?留言

?记忆

? 基于颜色特征的图像检索系统设计

入侵检测通信机制的设计?

基于算术编码的数据压缩算法研究与实现

?六月 25th, 2008

在现今的电子信息技术领域，由于需要处理的数字化的信息（尤其是多媒体信息）通常会特别庞大，如果不对其进行有效压缩就难以得到实际应用，数据压缩的目的即是通过有效减少数据文件的冗余信息而使数据文件可以以更快的速度传输或在更少的空间储存。因此数据压缩技术已成为当今数字通信、存储和多媒体娱乐的一项关键的共性技术。

本文由香农熵理论和统计编码的原理开始，逐步展开对基于算术编码的数据压缩的研究与应用的讨论：从算术编码的原理、产生条件、以及研究算术编码的目的意义等，到具体算术编码方案的分析比较以及其C++语言的实现方案，有重点的对算术编码的特点进行了分析和阐述。而针对算术编码在处理二元符号时高压缩比、低复杂度的特点，本文着重探讨了算术编码方法处理二元数据流的过程的特点和效率优势，并将算术编码的不同实现方法进行了分析和比较，特别是对N

阶自适应编码的特点和处理文字信息的优势进行了分析，然后将其和与之较为类似的Huffman编码进行了比较，通过比较得出了算术编码具有但Huffman编码不具有的在处理数据流方面的优势，即Huffman编码必须在得到全部数据文件之后才可以对文件进行编码处理，而算术编码方法可以在只得到数据流片段的情况下就开始对数据进行压缩，使得当处理数据流信息时在保证高压缩比的同时具有了很大的灵活性。

本文通过对算术算法特点和应用方向的研究，阐明其在数据压缩领域不可取代的地位及在处理流片段数据所具有的在压缩比和灵活性方面的优势，展示出算术编码的强大生命力和独特优势。

最后，应用文中研究得到的算术编码方法和实现模型，在Windows系统下，使用Visual C++ 作为编程工具，实现了算术编码及其应用程序界面，，对于接近二

进制流的文件，本设计具体令人满意的压缩效果，对其他格式的文件也有较好的压缩效果，达到了论文的设计目标。

关键词：算术编码、无损压缩、自适应模式

目录

摘要 II

ABSTRACT III

第一章绪论 1

1.1数据压缩 1

1.2数据压缩的现状与发展趋势 2

1.3课题研究的意义 4

第二章算术编码原理及特点 5

2.1统计编码 5

2.2算术编码原理 6

2.2.1算术编码理论 6

2.2.2算术压缩模式 8

第三章典型算术编码方案分析 12

3.1 WNC算法算术编码 12

3.2 基于上下文的二进制算术编码 14

3.3自适应算术编码算术及其实现 16

第四章算术编码系统的实现 20

4.1软件模块设计 20

4.2软件模块的具体实现 21

4.2.1输入输出模块的实现 21

4.2.2压缩模块的实现 24

4.2.3解压模块的实现 27

4.3压缩效率分析 30

4.4 软件设计的优点与不足 31

4.5 软件设计值得改进的地方 31

第五章算术编码总结 33

参考文献 35

致谢 36

附录 37

算法源代码 37

摘要

ABSTRACT

Nowadays, as the digital information (especially the multimedia information) becomes more voluminous in the telegraphy field, the information should be compressed availably. The purpose of data compression is reducing the redundancy of data files effectively for faster transfer and/or smaller space for storage. So the data compression technology becomes a common pivotal technology for digital communication,

storage and multimedia entertainment.

From Shannon entropy theory and the statistics coding theory, this paper sets forth the research and application of the data compression which based on Arithmetic Coding, including the arithmetic coding theory, the having conditions and the purpose of arithmetic coding and then the research of the specific implementation plan with C++ language of arithmetic coding. Against the point of arithmetic coding, this paper analysis and expounds its superiority about it . For the characteristic of the superiority of compression ratio and complexity, this paper probe into the process of deal with the binary data streams and the superiority of efficiency. And taking compared between the different implementation plan, especially the characteristic of Order-N adaptive coding and the superiority in dealing with the textual information. Then compares arithmetic coding with the Huffman coding method which is very resembles with it, getting the superiority in dealing with the data stream fragment: arithmetic coding doesn’t need the complete file before need to encode it, but Huffman coding method cannot do it like this. That means arithmetic do not only have the superiority in compression ratio but also in flexibility.

Through the research of the characteristic and the application direction of arithmetic coding, this paper illuminates the unplaced status of Arithmetic Coding, the outstanding compress ratio and agility in deal with data stream fragments and brings forth the life force and its unique superiority.

At last, by the arithmetic coding method and implement model researched in this paper, completed the coding method and its correspondingly application procedure interface using Visual C++ programming tools in the Windows operating system. The test result shows that to the files close to the binary files, this design procures a satisfactory outcome. And to the files in other format, this design also get a preferably results. So, the design achieves the goal required in this paper.

KEY WORDS arithmetic coding, lossless compression, adaptive model

第一章绪论

1.1数据压缩

数据压缩，用一句话说，就是用最少的数码来表示信号，即将字符串的一种表示方式转换为另一种表示方式，新的表示方式包含相同的信息量，但是长度比原来的方式尽可能的短。其作用是：能较快地传输各种信号，如传真、Modem通信等；在现有的通信干线并行开通更多的多媒体业务，如各种增值业务；紧缩数据存储容量，如CD－ROM、VCD和DVD等；降低发信机功率，这对于多媒体移动通信系统尤为重要。也就是说，通信时间、传输带宽、存储空间甚至发射能量，都可能成为数据压缩的对象。

数据之所以能够被压缩是基于以下几点的考量：

首先，数据中间常存在一些多余成分，既冗余度。如在一份计算机文件中，某些

符号会重复出现、某些符号比其他符号出现得更频繁、某些字符总是在各数据块中可预见的位置上出现等，这些冗余部分便可在数据编码中除去或减少。冗余度压缩是一个可逆过程，因此叫做无失真压缩，或称保持型编码。

其次，数据中间尤其是相邻的数据之间，常存在着相关性。如图片中常常有色彩均匀的背影，电视信号的相邻两帧之间可能只有少量的变化影物是不同的，声音信号有时具有一定的规律性和周期性等等。因此，有可能利用某些变换来尽可能地去掉这些相关性。但这种变换有时会带来不可恢复的损失和误差，因此叫做不可逆压缩，或称有失真编码、摘压缩等。

此外，人们在欣赏音像节目时，由于耳、目对信号的时间变化和幅度变化的感受能力都有一定的极限，如人眼对影视节目有视觉暂留效应，人眼或人耳对低于某一极限的幅度变化已无法感知等，故可将信号中这部分感觉不出的分量压缩掉或”掩蔽掉”。这种压缩方法同样是一种不可逆压缩。

数据压缩跟编码技术联系紧密，压缩的实质就是根据数据的内在联系将数据从一种编码映射为另一种编码。压缩前的数据要被划分为一个一个的基本单元。基本单元既可以是单个字符，也可以是多个字符组成的字符串。称这些基本单元为源消息，所有的源消息构成源消息集。源消息集映射的结果为码字集。可见，压缩前的数据是源消息序列，压缩后的数据是码字序列。

若定义块为固定长度的字符或字符串，可变长为长度可变的字符或字符串，则编码可分为块到块编码、块到可变长编码、可变长到块编码、可变长到可变长编码等。应用最广泛的ASCII编码就是块到块编码。对于数据压缩技术而言，最基本的要求就是要尽量降低数字化的在码事，同时仍保持一定的信号质量。不难想象，数据压缩的方法应该是很多的，但本质上不外乎上述完全可逆的冗余度压缩和实际上不可逆的嫡压缩两类。冗余度压缩常用于磁盘文件、数据通信和气象卫星云图等不允许在压缩过程中有丝毫损失的场合中，但它的压缩比通常只有几倍，远远不能满足数字视听应用的要求。在实际的数字视听设备中，差不多都采用压缩比更高但实际有损的媳压缩技术。只要作为最终用户的人觉察不出或能够容忍这些失真，就允许对数字音像信号进一步压缩以换取更高的编码效率。摘压缩主要有特征抽取和量化两种方法，指纹的模式识别是前者的典型例子，后者则是一种更通用的摘压缩技术。

1.2数据压缩的现状与发展趋势

设计具体的压缩算法时，设计者首先要做的是寻找一种能尽量精确地统计或估计信息中符号出现概率的方法，然后还要设计一套用最短的代码描述每个符号的编码规则。统计学知识对于前一项工作相当有效，迄今为止，人们已经陆续实现了静态模型、半静态模型、自适应模型、Markov模型、部分匹配预测模型等概率统计模型。

第一个实用的编码方法是由 D. A. Huffman 在 1952 年的论文”最小冗余度代码的构造方法”[1]中提出的。直到今天，许多”数据结构”教材在讨论二叉树时仍要提及这种被后人称为 Huffman 编码的方法。 Huffman 编码看似简单，但却影响深远，其编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。

1968 年前后， P. Elias[2] 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissanen[3] 提出了一种可以成功地逼近信息熵极限的编码方法–算术编码。 1982 年， Rissanen 和 G. G. Langdon[4] 一起改进了算术

编码。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten[5] 于 1984 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为 PPMC 、 PPMD 或 PPMZ 并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。

犹太人 J. Ziv 和 A. Lempel脱离 Huffman 及算术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。这些算法统称为 LZ 系列算法，如： LZ77 算法， LZ78 的压缩算法，以及LZW 算法。该系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。这种基于字典模型的思路在表面上虽然和 Shannon 、 Huffman 等人开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且LZ 系列算法在本质上符合信息熵的基本规律。 LZ 系列算法的优越性使得使用该算法的压缩软件数量呈爆炸式增长。今天，我们熟悉的 PKZIP 、 WinZIP 、 WinRAR 、Gzip 等压缩工具以及 ZIP、GIF、PNG 等文件格式都是 LZ 系列算法的受益者。

在图像压缩领域，著名的 JPEG 标准是有损压缩算法中的经典。 JPEG 标准由静态图像联合专家组（ Joint Photographic Experts Group ， JPEG ）于 1986 年开始制定，1994 年后成为国际标准。 JPEG 以离散余弦变换（ DCT ）为核心算法，通过调整质量系数控制图像的精度和大小。

CCITT 于 1988 年制定了电视电话和会议电视的 H.261 建议草案。 H.261 的基本思路是使用类似 JPEG 标准的算法压缩视频流中的每一帧图像，同时采用运动补偿的帧间预测来消除视频流在时间维度上的冗余信息。在此基础上， 1993 年，ISO 通过了动态图像专家组（ Moving Picture Experts Group ， MPEG ）提出的 MPEG-1 标准。 MPEG-1 可以对普通质量的视频数据进行有效编码。为了支持更清晰的视频图像，特别是支持数字电视等高端应用， ISO 于 1994 年提出了新的 MPEG-2 标准（相当于 CCITT 的 H.262 标准）。 MPEG-2 对图像质量作了分级处理，可以适应普通电视节目、会议电视、高清晰数字电视等不同质量的视频应用。在我们的生活中，可以提供高清晰画面的 DVD 影碟所采用的正是MPEG-2 标准。

Internet 的发展对视频压缩提出了更高的要求。ISO 于1999年通过了 MPEG-4 标准（相当于 CCITT 的 H.263 和 H.263+ 标准）。 MPEG-4 标准拥有更高的压缩比率，支持并发数据流的编码、基于内容的交互操作、增强的时间域随机存取、容错、基于内容的尺度可变性等先进特性。音频数据的压缩技术最早是由无线电广播、语音通信等领域里的技术人员发展起来的。这其中又以语音编码和压缩技术的研究最为活跃。自从 1939 年 H. Dudley 发明声码器以来，人们陆续发明了脉冲编码调制（ PCM ）、线性预测（ LPC ）、矢量量化（ VQ ）、自适应变换编码（ ATC ）、子带编码（ SBC ）等语音分析与处理技术。这些语音技术在采集语音特征，获取数字信号的同时，通常也可以起到降低信息冗余度的作用。为获得更高的编码效率，大多数语音编码技术都允许一定程度的精度损失。而且，为了更好地用二进制数据存储或传送语音信号，这些语音编码技术在将语音信号转换为数字信息之后又总会用 Huffman 编码、算术编码等通用压缩算法进一步减少数据流中的冗余信息。

很显然，在多媒体信息日益成为主流信息形态的数字化时代里，数据压缩技术特别是专用于图像、音频、视频的数据压缩技术还有相当大的发展空间–毕

竟，人们对信息数量和信息质量的追求是永无止境的。

1994年， M. Burrows 和 D. J. Wheeler 共同提出了一种全新的通用数据压缩算法。这种算法的核心思想是对字符串轮转后得到的字符矩阵进行排序和变换，类似的变换算法被称为 Burrows-Wheeler 变换，简称 BWT 。与 Ziv 和 Lempel 另辟蹊径的做法如出一辙， Burrows 和 Wheeler 设计的 BWT 算法与以往所有通用压缩算法的设计思路都迥然不同。如今， BWT 算法在开放源码的压缩工具bzip 中获得了巨大的成功， bzip 对于文本文件的压缩效果要远好于使用 LZ 系列算法的工具软件。这至少可以表明，即便在日趋成熟的通用数据压缩领域，只要能在思路和技术上不断创新，我们仍然可以找到新的突破口。

分形压缩技术是图像压缩领域近几年来的一个热点。这一技术起源于 B. Mandelbrot 于 1977 年创建的分形几何学。 M. Barnsley 在 20 世纪 80 年代后期为分形压缩奠定了理论基础。从 20 世纪 90 年代开始， A. Jacquin 等人陆续提出了许多实验性的分形压缩算法。今天，很多人相信，分形压缩是图像压缩领域里最有潜力的一种技术体系，但也有很多人对此不屑一顾。无论其前景如何，分形压缩技术的研究与发展都提示我们，在经过了几十年的高速发展之后，也许，我们需要一种新的理论，或是几种更有效的数学模型，以支撑和推动数据压缩技术继续向前跃进。

人工智能是另一个可能对数据压缩的未来产生重大影响的关键词。既然 Shannon 认为，信息能否被压缩以及能在多大程度上被压缩与信息的不确定性有直接关系，假设人工智能技术在某一天成熟起来，假设计算机可以像人一样根据已知的少量上下文猜测后续的信息，那么，将信息压缩到原大小的万分之一乃至十万分之一，恐怕就不再是天方夜谭了。

人们总喜欢畅想未来，但未来终究是未来，对未来的预测其主要基准还是我们现有的应用技术和思维模式，未来技术的发展存在着诸多的不可预测性，但终究离不开现有的技术基础，所以这就是本文所作对压缩算法进行研究和应用探讨的意义所在。

1.3课题研究的意义

电脑里的数据压缩的主要功用有两个：第一，可以节省存储空间；第二，可以在通信过程中减少对带宽的占用。虽然随着存储技术的快速发展，电脑的主存储器、辅助存储器的容量以及数据通信的带宽都有了很大提高，但如何在相同的空间存储更多的信息以及在已有的带宽情况下，更快捷的传输更多的信息，仍主要取决于数据压缩技术的发展。如果没有数据压缩技术，那我们每次对数据信息进行提取和操作，与现在相比，将是个漫长复杂的过程，更无法在短时间内对海量信息进行检索，而视频和音频信息也将是人类信息交换的巨大负担。

为方便信息的存储、检索和使用，在进行信息处理时赋予信息元素以代码的过程。编码的目的在于提高信息处理的效率。信息编码必须标准、系统化。设计合理的编码系统是关系信息管理系统生命力的重要因素。信息编码的基本原则是在逻辑上要满足使用者的要求，又要适合于处理的需要；结构易于理解和掌握；要有广泛的适用性，易于扩充。一般应有的代码有两类，一类是有意义的代码，即赋予代码一定的实际意义，便于分类处理；一类是无意义的代码，仅仅是赋予信息元素唯一的代号，便于对信息的操作。在通信理论中，编码是对原始信息符号按一定的数学规则所进行的变换。编码的目的是要使信息能够在保证一定质量的条件下尽可能迅速地传输至信宿。

第二章算术编码原理及特点

2.1统计编码

数据压缩可以分为可逆的无失真编码和不可逆的有失真编码两大类基本方法[6]。因为大多数计算机文件都不允许在压缩过程中丢失信息，所以对各种信源都通用的可逆压缩方法就显得更为重要，这类方法主要利用消息或消息序列出现的概率的分布特性，注重寻找概率与码字长度间的最优匹配，叫做统计编码或概率匹配编码，统称为熵编码。

计算机文件表现为字符集合（如文本）或二进制符号（一般为0和1）集合。两者的最终形式都是”0″、”1″代码，只是前者一般用ASCII码编码表示。文本文件包括电报报文、程序指令等，一般由10进制数字0~9、英文字母及$、*、&等特殊符号组成，对其压缩必须”透明”，即恢复后的文件不许有任何失真。一个符号错误就可能产生灾难性的后果，例如数据库中包含有金融交易，或者控制系统的可执行程序。

对于文本文件，有物理压缩和逻辑压缩两种方法，逻辑压缩实际上只是一种由数据自身特点及设计者技巧来决定的”压缩表示法”，并不具有普遍性，而物理压缩方法则是通过减少计算机文件内部冗余度的方法来实现对源文件的压缩，而信源中的冗余度的表现形式包括：字符分布(character distribution)、字符重复(character repetition)、高使用率模式(high-usage patterns)以及位置冗余(positional redundancy)

香农定理[7]描述了有限带宽;有随机热噪声信道的最大传输速率与信道带宽; 信号噪声功率比之间的关系.

在有随机热噪声的信道上传输数据信号时，数据传输率Rmax与信道带宽B，信噪比S/N关系为： Rmax=B×log2（1+S/N）在信号处理和信息理论的相关领域中，通过研究信号在经过一段距离后如何衰减以及一个给定信号能加载多少数据后得到了一个著名的公式，叫做香农（Shannon）定理。它以比特每秒（bps）的形式给出一个链路速度的上限，表示为链路信噪比的一个函数，链路信噪比用分贝（dB）衡量。因此我们可以用香农定理来检测电话线的数据速率。

香农定理由如下的公式给出: C=Blog2(1＋S/N) 其中C是可得到的链路速度，B 是链路的带宽，S是平均信号功率,N是平均噪声功率，信噪比（S/N）通

常用分贝（dB）表示，分贝数=10×log10（S/N）。

讨论熵编码就必需要了解熵（entropy)的概念：(1)熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数字上就是概率越小。

(2)某个事件的信息量用 =-logi 表示，其中为第i个事件的概率，0<1 。香农理论的重要特征即是熵的概念，他证明熵与信息内容的不确定程度有等价关系。熵曾经是波尔兹曼在热力学第二定律引入的概念，我们可以把它理解为分子运动的混乱度。信息熵也有类似意义，例如在中文信息处理时，汉字的静态平均信息熵比较大，中文是9.65比特，英文是4.03比特。这表明中文的复杂程度高于英文，反映了中文词义丰富、行文简练，但处理难度也大。信息熵大，意味着不确定性也大。

按照香农的理论[7]，信源S的熵的定义为H（S）= = log(1/其中是符号在

S中出现的概率；lo (1/表示包含在中的信息量，也就是编码所需要的位数。例如，一幅用256灰度级表示的图像，如果每一个象素点灰度的概率均为

=1/256，编码每一个象素点就需要8位。熵作为理论上的平均信息量，即编码一个信源符号所需的二进制位数，在实际的压缩编码中的码率很难达到熵值，不过

熵可以作为衡量一种压缩算法的压缩比好坏的标准，码率越接近熵值，压缩比越高。由于在许多场合，开始不知道要编码数据的统计特性，也不一定允许你事先知道它们的编码特性，因此算术编码在不考虑信源统计特性的情况下，只监视一小段时间内码出现的概率，不管统计是平稳的或非平稳的，编码的码率总能趋近于信源的熵值。实现算术编码首先需要知道信源发出每个符号的概率大小，然后再扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。

2.2算术编码原理

算术编码是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman 编码效率提高10 %左右,但由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不像Huffman 编码那样应用广泛。国外对算术编码的研究较多,取得了许多重要的应用,但大多都有专利保护,如JPEG、JBIG和H. 261 中均采用了算术编码;国内的研究相对较少,应用不是很广泛,许多人还不了解。随着算术编码实现技术的改进,必将以其独特的优良性能成为无失真压缩方法的主流。

算术编码的处理过程会产生一个位数逐步增加的实数, 该实数所对应的概率区间对应着编码信息。这个实数的值稍有变化, 其对应的概率区间就会改变, 导致解不出原来的信息, 后面译出的码字全部错误. 这就是算术编码的重要特点: 算术编码是非分组码[6] , 编码器是有记忆的, 编码输出流被看作一个不可分割的整体. 这个特点不仅带来严重的误码扩散问题, 而且给算术编码的灵活应用带来了很大困难. 其他的压缩算法, 像Huffman 算法、LZW 算法等, 是分组码, 各输出码字之间是独立的, 误码不易扩散. 对于算术编码,从对其基本原理的讨论中看到, 它的编码输出流中是不能随意嵌入冗余编码等附加信息的.算术编码的思想可以追溯到1948 年Shannon 的论文[7 ]中,20 世纪60 年代初

期,Elias 给出了一个递推公式[2 ] ,使得算术编码向实用化方向前进了一大步。但此时的算术编码需要无限精度的浮点运算,这对于当时的技术和实用化进程是一个无法克服的障碍。70 年代, Rissanen[3 ] 和 Pasco 分别提出了用有限精度逼近的算法,从此算术编码开始进入实用化阶段。进入80 年代,算术编码的研究达到高潮。Rubin、Rissanen 和 Langdon[4] 等人在此期间对算术编码作了大量的理论研究,并给出了一个二进制的算术编码器,Witten 等人给出了一个通用的算术编码器。90 年代以来,算术编码的理论已基本成熟,主要研究工作放在算法的实现技术的改进和应用上。算术编码可以以分数比特逼近信源的熵,统计模型可以与算法很好地分离,易于实现自适应模式,因此编码算法流畅完美,效率很高。

2.2.1算术编码理论

算术编码(arithmetic coding)是一种无损数据压缩方法，也是一种熵编码的方法[6]。和其它熵编码方法不同的地方在于算术编码跳出了分组编码的范畴，

从全序列出发，采用递推形式的连续编码，它不是将单个的信源符号映射成一个码字，而是将整个输入符号序列映射为实数轴上[0,1)区间内的一个小区间，其长度等于该序列的概率；再在该小区间选择一个代表性的二进制小数，作为实际的编码输出，从而达到了高效编码的目的，不论是否二元信源，也不论数据的概率分布如何，其平均码长均能逼近信源的熵。

早在1948年，香农[7]就提出将信源符号依其概率降序排序，用符号序列累积概率的二进制表示作为对信源的编码，并从理论上谁了它的优越性；1960年后，

P.Elias发现无需排序，只要编、解码端使用相同的符号顺序即可。但当时人们仍然认为算术编码需要无限精度的浮点运算，或随着符号的输入，所需的计算精度和时间也相应增加。1976年，R.Pasco和J.Rissanen[3]分别用定长的寄存器实现了有限精度的算术编码，但仍无法实用，因为后者的方法是”后入先出”(LIFO)的，而前者的方法跃然是”先入先出”(FIFO)的，但却没有解决有限精度计算所固有的进位问题，1979 年Rissanen和https://www.sodocs.net/doc/d1734125.html,ngdon[4]一起将算术编码系统化，并于1981年实现了二进制编码。1987年Witten[5]等人了一个实用的算术编码程序，即CACM87(后用于ITU-T的H.263视频压缩)；同期IBM公司发表了著名的Q－编码器(后用于JPEG、JPEG2000和JBIG 图像压缩标准),从此算术编码迅速得到了广泛的注意。

算术编码的基本原理是[6]：根据信源可能发现的不同符号序列的概率，把 [0，1)区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。使用算术编码方法进行多元符号编码时，算术编码每次递推都要做乘法，而且必须在一个信源符号周期内完成，有时就难以实时，为此采用了查表等许多近似计算来代替乘法，但若编码对象本身就是二元序列，且其符号概率较小者为p(L)=2-Q形式，其中Q是正整数，称作不对称数(skew number),则乘以2-Q可代之以右移Q位，而乘以符号较大者p(H)=1-2-Q 可代之以移位和相关，这样就完全避免了乘法。因此算术编码很适合二元序列，而p(L)常用2-Q来近似。，随着输入序列，长度的增加，编成C(s)的长度也随之不断增加，而实际只能用有限长的寄存器C，这就要求将C中已编码的高位码字及时输出。但又不能输出过早，以免后续运算还需调整已输出的。不难想象，当C中未输出部分各高位均为"1"时，则低位运算略有增量，就可

能进位到已输出部分，特别是当这种连"1"很长时，这就是有限精度算术编码

所固有的进位问题。Rissanen和Langdon利用插入1个额外的"0"(即所谓"填

充位")来隔断进位的扩展，对编码效率会略有影响。类似地，对于区间宽度A(s)，也只能基于有限位数的寄存器A来实现。对于算术的编解码来说，不对称数Q(s) 是一个重要参数，当时假定它是根据信源概率模型已事先确定的一个量，要从一个二进制序列s来确定Q值，有待于根据该序列的统计特性，选择合适的概率模型，譬如根据符号串s后面出现字符l条件概率 p(L|s)~=2-Q来确定Q值。而当实际上"0"和"1"都有可能成为符号位数值时，应该随着它们在被编码符号串中出现的概率而自适应地改变。算术编码器在每一步都需要知道用于下一个待编码符号的Q(s)值，以及指出哪个符号是L符号，通常串中字符发生的概率与序列的概率模型有关，因此算术编码应用的另一个问题，就是快速自适应地估计条件概率p(L|s)，从信源的统计特性出发，建立数据的概率模型。而算术编码

的最大优点之一，就是具有自适应功能，高二进制信源的字母表主(0,1)，算术编码在初始化预置一个大概率P和一个小概率Q，随着输入版本号概率的变化，自动修改Q或P的值。一般假定初始值Q=0.5，当后继输入连续为H符号时，Q 值渐渐减小，若连续出现L符号时，Q值增加。增加到超过0.5时，Q和P对应的符号相互交换。因此，使用算术编码不必预告定义信源的概率模型，尤其适用于不可能进行概率统计的场合。

Huffman 编码的一个不足是译码复杂度高，由于事先不知道码长，Huffman码表

实质上是一棵二进制树，解析每一码字的基本方法就是从树根开始，集资根据面临的每一位是0还是1来决定沿哪一半子树继续译码，直到端节点，这样在运算时就要对码字的每位做出逻辑判决。基要求译码器与一个传输速率为200Mb/s

的磁盘驱动器。

要使其相适应而不导致系统瓶颈，则判决逻辑的时钟至少不能低于该速率。这并非不能实现，但却不那么简单。通常对于用变长码压缩的大容量数据，解码系统的性能价格比不会最高。而在实现上，算术编码要比霍夫曼编码更复杂，特别是硬件实现时。

算术编码也是变长码，编码过程中的移位和输出都不均匀，也需要缓存，在误差扩散方面，也比分组码更严重；在分组码中，由于误码而破坏分组，过一会儿常能自动恢复们是不在算术码中却往往会一直延续下去，因为它是从全序列出发来编码的。因而算术码流的传输也要求高质量的信道，或采用检错反馈重发的方式。各种媒体信息（特别是图像和动态视频）数据量非常之大。例如：一幅640x480分辨率的24位真彩色图像的数据量约力9O0kb；一个1O0Mb的硬盘只能存储约l00幅静止图像画面。显然，这样大的数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传输速率所不及的。因此，为了存储、处理和传输这些数据，必须进行压缩。相比之下，语音的数据量较小，且基本压缩方法己经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。图像压缩技术、视频技术与网络技术相结合的应用前景十分可观，如远程图像传输系统、动态视频传输可视电话、电视会议系统等己经开始商品化，MPEG标准与视频技术相结合的产物一家用数字视盘机和VCD系统等都已进入市场。可以预计，这些

技术和产品的发展将对本世纪末到二十一世纪的社会进步产生重大影响。而算术编码作为一种高效的数据编码方法在文本，图像，音频等压缩中有广泛的应用，所以，研究算术编码以更好的利用它是非常必要的。

2.2.2算术压缩模式

算术编码对整条信息（无论信息有多么长），其输出仅仅是一个数，而且是一个介于 0 和 1 之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数 0.1010001111，也即十进制数 0.64。

下面借助一个简单的例子来阐释算术编码的基本应用原理。为了表示上的清晰，我们暂时使用十进制表示算法中出现的小数，这丝毫不会影响算法的可行性。考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的信息

为 bccb。

在没有开始压缩进程之前，假设我们对 a b c 三者在信息中的出现概率一无所知（我们采用的是自适应模型），没办法，我们暂时认为三者的出现概率相等，也就是都为 1/3，我们将 0 - 1 区间按照概率的比例分配给三个字符，即 a 从 0.0000 到 0.3333，b 从 0.3333 到 0.6667，c 从 0.6667 到 1.0000。用图形表示就是：

+-- 1.0000

|

Pc = 1/3 |

|

+-- 0.6667

|

Pb = 1/3 |

|

+-- 0.3333

|

Pa = 1/3 |

|

+-- 0.0000

现在我们得到第一个字符 b，来看 b 对应的区间 0.3333 - 0.6667。这时由于多了字符 b，三个字符的概率分布变成：Pa = 1/4，Pb = 2/4，Pc = 1/4。让我们按照新的概率分布比例划分 0.3333 - 0.6667 这一区间，划分的结果可以用图形表示为：

+-- 0.6667

Pc = 1/4 |

+-- 0.5834

|

Pb = 2/4 |

|

+-- 0.4167

Pa = 1/4 |

+-- 0.3333

接着我们拿到字符 c，我们现在要关注上一步中得到的 c 的区间 0.5834 - 0.6667。新添了 c 以后，三个字符的概率分布变成 Pa = 1/5，Pb = 2/5，Pc = 2/5。我们用这个概率分布划分区间 0.5834 - 0.6667：

+-- 0.6667

|

Pc = 2/5 |

|

+-- 0.6334

|

Pb = 2/5 |

|

+-- 0.6001

|

Pa = 1/5 |

|

+-- 0.5834

现在输入下一个字符 c，三个字符的概率分布为：Pa = 1/6，Pb = 2/6，Pc = 3/6。我们来划分 c 的区间 0.6334 - 0.6667

+-- 0.6667

|

Pc = 3/6 |

|

+-- 0.6501

|

Pb = 2/6 |

|

+-- 0.6390

|

Pa = 1/6 |

|

+-- 0.6334

输入最后一个字符 b，因为是最后一个字符，不用再做进一步的划分了，上一步中得到的 b 的区间为 0.6390 - 0.6501，好，让我们在这个区间内随便选择一个容易变成二进制的数，例如 0.64，将它变成二进制 0.1010001111，去掉

前面没有太多意义的 0 和小数点，我们可以输出 1010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算术压缩过程。

解压缩是压缩的逆过程解压缩之前我们仍然假定三个字符的概率相等，并得

出上面的第一幅分布图。解压缩时我们面对的是二进制流 1010001111，我们先在前面加上 0 和小数点把它变成小数 0.1010001111，也就是十进制 0.64。这时我们发现 0.64 在分布图中落入字符 b 的区间内，我们立即输出字符 b，并得出三个字符新的概率分布。类似压缩时采用的方法，我们按照新的概率分布划分字符 b 的区间。在新的划分中，我们发现 0.64 落入了字符 c 的区间，我们可以输出字符 c。同理，我们可以继续输出所有的字符，完成全部解压缩过程（为了叙述方便，我们暂时回避了如何判断解压缩结束的问题，实际应用中，这个问题并不难解决）。

对以上论述进行归纳，我们可以得到算术编码的特点是：

1）不必预先定义概率模型，自适应模式具有独特的优点；

2）信源符号概率接近时，此时算术编码效率高于其他编码方法。

3）算术编码绕过了用一个特定的代码替代一个输入符号的想法，用一个浮点输出数值代替一个符号流的输入。

算术编码虽然具有其独特的优点，但我们仍需要注意下面几个问题：

1）由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。

2）算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。

3）算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。

算术编码是一种高效的熵编码方案，其每个符号所对应的码长被认为是分数[8]。由于对每一个符号的编码都与以前编码的结果有关，所以它考虑的是信源符号序

列整体的概率特性，而不是单个符号的概率特性，因而它能够更大程度地逼近信源的极限熵，降低码率。

第三章典型算术编码方案分析

3.1 WNC算法算术编码

WNC算法建立模型的过程是这样的：

（1）由于英文字符一共有256个，建立两个257个元素的数组 cum_freq[] 和freq[]，其中第257个元素是结束标志。cum_freq[] 是将输入符号按照出现概

率的大小进行顺序排列，freq[]用于积累输入符号的出现频率。初始化时由于每个符号的出现概率是一样的，freq[]均为1，cum_freq[]按照从256到0的顺序排列。

（2）更新模型的时候首先要判断是否积累的频率超出了预定的范围，如果超出了的话，就需要将每个符号的出现频率减少一半；如果没有超出就进行下一步。接下来是重新排序，保证当前输入符号按照出现频率有着正确的顺序，最后就可以增加输入符号的出现概率了，此时不但需要增加对应的 freq[] ，而且需要增加对应的cum_freq[]之前的所有值。因为 cum_freq[] 是最终用来计算输入符号的概率的。

二进制索引树的数据结构，下图所示。

图3.2 二进制索引树结构

根据二进制索引树可以建立这样的一个前后关系，称节点a是节点b的前节点，它们满足：a=forw(b),节点c是节点d的后节点,它们满足 c=back (d) ，其中forw (),back()如下

forw (i)=i+i&(-i)

back (i)=i&(i-1)

下面的算法采用BIT这种数据结构来组织数据，更新模型表。过程是这样的：（1）按照WNC算法中建立模型的方法一样建立一个关于输入符号的模型，在这里一点不同的是只需要 cum_freq[] 来积累输入符号的出现频率。初始化时由于每个符号的出现概率是一样的， cum_freq[] 按照从最大值到0 的顺序排列。（2）更新模型中的元素时，由于已经建立的前后关系，只需要更新该元素的积累频率及其之后的元素的积累频率。

（3）判断是否积累的频率超出了预定的范围，如果超出了的话，就需要根

据前后关系，将每个符号的积累频率减少一半。需要注意的是由于更新是按照前后关系进行的，所以减少的过程也需要按照这样的顺序进行。

整个编码器的框图如下：

图3.3 WNC算法编解码流程图

其中install, update_model 的过程如上所述，encode_symbol部分的具体算法流程如下：

（1）计算此时区间的范围和上界、下界。

范围range=high-low+1

新的上界：high=low+range×cum_freq{back(symbol)}/cum_feq[0]-1

新的下界：low=low+range×cum_freq[symbol]/cum_freq[0]

（2）根据（1）计算的上界、下界输出比特，以下的过程在一个循环中反复进行，直到跳出。

i) 如果上界小于初始区间的一半，输出0；

ii) 如果下界大于或等于初始区间的一半，输出1，同时将区间向下移一半，也就是low=low-HALF ; high=high-HALF

iii) 如果下界大于或等于初始区间的1/4并且上界小于初始区间的3/4，输出一个与前一个输出位相反的跟随位，并且将区间向下移1/4，low=low-QUARTER,

high=high-QUARTER;

iv) 如果不在上面的情况中，停止输出，跳出循环，否则的话，扩大当前区间的上下界（因为已经输出了表示位），low=2×low, high=2×high+1。

虽然WNC算法可以很好地解决算术编码的概率预定义问题，但是它又不可避

免的带来了新的问题，就是关于模型更新以及查找该符号时所带来的庞大计算量的问题。

3.2 基于上下文的二进制算术编码

基于上下文的自适应二进制算术编码 (CABAC）是一种体现了新思想、具备新特点的新型二进制算术编码方法。它的主要面对视频流的相关统计特性，其特点在于采用了高效的算术编码思想，充分考虑视频流的数据特点，大大提高了编码效率，针对视频数据流处理的H.264/AVC即采用了这种新的二进制算术编码。CABAC的基本编码步骤可分为三步：1. 二进制化；2. 上下文建模；3. 二进制算术编码。第一步主要是将非二进制的各语法元素值转换成二进制的比特序列，如果语法元素本身是二进制的，则该步骤可省略；第二步主要是为已二进制化的语法元素的比特序列的每一位提供概率模型，进行概率预测；第三步则进行二进制算术编码，在CABAC 中，有两种编码模式，一种叫做regular coding mode，另一种叫做by pass coding mode，其中regular coding mode采用了上下文建模，而by pass coding mode为了加快编码速度不采用上下文建模，整个编码过程如下图所示。

图3.4 CABAC编码流程图

CABAC基本步骤简述：

首先是二进制化：为了降低算术编码的复杂度，提高编码速度，CABAC 采用了二进制的算术编码，而非其它多进制的算术编码，为此需要事先将每一语法元素转换成独一无二的二进制序列，在 H.264 中称 BIT STRING，同时为了便于后面的算术编码，尽可能降低编码复杂度，应该尽可能减小二进制序列的大小，CABAC 采用了4 种基本二进制转换方式：Unary Binarization, Truncated unary Binarization, kth order Exp-Golomb Binarization 和 Fixed-length Binarization,相应的有4种二进制码Unary code, Truncated unary code, kth order Exp-Golomb code 和 Fixed-length code。

接下来是上下文建模部分：所谓上下文建模，就是建立概率模型，对每一位

待编码的比特值和概率进行预测。这些模型可分为4 种类型. 第1 种类型的模型必须根据它相邻的已编码的语法元素构成。第2种模型仅局限于对宏块类型和子宏块类型的应用。第3 种和第4 种模型仅用于残余数据的编码。下表给出了H264/AVG 中的所有语法元素和它们所用到的上下文模型索引的对应关系。

语法元素(SE)

片类型(Slice type)

SI I P,SP B

mb_skip_flag –– 11~13 24~26

mb_field_decoding_flag 70~72 70~72 70~72 70~72

mb_type 0~10 3~10 14~20 27~35

moded_block_pattern(luma) 73~76 73~76 73~76 73~76

coded_block_pattern(chroma) 77~84 77~84 77~84 77~84

mb_qp_delta 60~63 60~63 60~63 60~63

prev_intra4×4_pred_mode_flag 68 68 68 68

rem_intre4×4_pred_mode 69 69 69 69

intra_chroma_pred_mode 64~67 64~67 64~67 64~67

ref_idx –– 54~59 54~59

mvd(horizontal) –– 40~46 40~46

mvd(vertical) –– 47~53 47~53

sub_mb_type –– 21~23 36~39

coded_block_flag 85~104 85~104 85~104 85~104

significant_coeff_flag[] 105~165

277~337 105~165

277~337 105~165

277~337 105~165

277~337

last_significant_coeff_flag[] 166~266

338~398 166~266

338~398 166~266

338~398 166~266

338~398

coeff_abs_level_minus1[] 227~275 227~275 227~275 227~275

表3.3 语法元素索引表

其中r从0~72 是关于宏块类型、子宏块类型、预测模式以及基于片层和宏块层的控制信息等语法元素的上下文模型索引，对于这种类型的语法元素，其索引值’由公式r=Ts+xs计算。式中：Ts代表上下文索引的初值，也就是表中所给出的值，xs代表其增量值。它依赖于待编码比特位的索引值。 r从73~398 是残余数据的编码,其中语法元素coded_block_pattern的上下文模型索引值r 计算公式同上，而其它残余数据语法元素的上下文模型索引值则由公式

r=Ts+Qs(ctx_cat)+xs给出。式中：Qs(ctx_cat)值由语法元素及其上下文范畴(con-text category, 简称ctx-cat决定，具体值可见下表。值得一提的是在纯帧或纯场编码中，仅实际乃至个模型中的277个。

语法元素上下文范畴(ctx-cat)

0 1 2 3 4

coded_block_flag 0 4 8 12 16

significant_coeff_flag 0 15 29 44 47

last_significant_coeff_flag 0 15 29 44 47

coeff_abs_level_minus1 0 10 20 30 39

表3.4 语法元素与上下文范畴对应表

二进制算术编码：在CABAC中$对每一待编码的比特位的值(0 或)，用MPS和LPS 表示，其中MPS（ most probable symbol）表示最可能出现的状态，对应0 和1 中概率大的那一个；LPS（least probable symbol）表示最不可能出现的状态，对应0 和1 中概率小的那一个。这样只需要一个变量值pσ保存LPS出现的概

率大小，对应MPS出现的概率大小可由(1-pσ)表示。同时，它把概率pσ量化成64个等级，每一概率pσ由其对应的索引σ唯一给出。这样在CABAC中，每一个上下文模型可由两个变量唯一决定，一个是LPS 的概率值pσ，一个是MPS 的值用ω表示。由于CABAC中，pσ值被量化成64 个等级，同时，ω值在二进制编码中只有0 和1 两种取值。因此在CABAC 中一共只有128 种概率状态, 可用7 比特来表示。

在H.264中，片层是自适应编码的基本单元，在一个片层数据编码完，新的片层数据到来时，CABAC要对各概率状态进行重新初始化，初始化的重要依据QP参数，各片层的QP参数不同，则在初始化时各概率状态值是不同的。

虽然基于上下文的自适应二进制算术编码算法可以很好地解决算术编码的自适应问题，但是它也不可避免的带来了新的问题，就是关于符号概率表的储存以及查找该符号概率时所带来的复杂度增加的问题。

3.3自适应算术编码算术及其实现

所谓自适应算术编码是在算术编码基本原理的基础上，根据信源数据来自不同符号集的特性，充分利用信源数据的统计特性，将每种类型的数据分开处理，各自拥有一个独立的统计模型单元，可以得到更高的编码效率。同时利用各种进制数据进行转换的时机,将压缩数据分成不同的数据段,将误码限制在本数据段内,当误码产生时,其影响最多从误码位到本段结束位处[10]。

现在来看一下符号的概率问题：在所有情况下，每种可能的概率都落在区间[0,1)中，而所有概率的和则为1.这个区间包含了所有概率的可能，所以我们可以以此来对序列进行编码。每个概率会落到此区间的一个子区间，对一个序列重复这样编码，就会得到关于这个消息的一个特定区域。这个区间的任何一个数字都可以成为一个有效的编码。设为PM(ai)某序列中ai的概率。因为概率之和总是为1，那现在就让我们用这个数来划分区间[0,1)每个数所划分的区间大小取决于它的概率。

设某序列有四个字符a,b,c,d;其各自概率如下

PM(a)=0.5,PM(b)=0.25,PM(c)=0.125,PM(d)=0.125

我们设变量high和low来表示区间的上下限，之后依照概率的变化，对上

下限进行修正，从上图我们得到如下概率区间：

high 1.0 K(0) 0.0 K(2) 0.75

low 0.0 K(1) 0.5 K(3) 0.875

表3.1 预设字符序列的概率表

我们假设字符是按照一个固定的概率表出现的，这种模式现实中确实存在，我们称之为静态模式。

编码的第一步是初始化区间I:=[low,high)by low=0 and high =1，当读取s1后，区间将被重新划分为I',而它的上下限还是叫做high和low。

将新的区间I'映射到中[low,high)，这完全是按照上表的统计特性来计算的。产生更短代码字的片断数越少，区间I'就越大。然后在新区间重复前面的过程。当接收新符号时，区间I'的划分是以low为新下限的，

以上规则对每一步都适用，都是由第一步 low =0且 high － low ＝1

得到的。因为我们不再需要旧的high和low的值，所以我们要重写它们：

low := low'

:=high'

设我们要编码的序列为abaabcda第一步如下：

low = 0

high = 0＋0.5?1 =0.5

新区间变成了然后对b编码：

low = 0＋0.5?（0.5-0）=0.25

high = 0+0.5?（0.5-0）＋0.25?（0.5-0）=0.375

a：

low = 0.25

high = 0.25+0.5?（0.375-0.25）=0.3125

a ：

low = 0.25

high = 0.25＋0.5?（0.3125-0.25）=0.28125

b：

low = 0.25+0.5?（0.28125-0.25）=0.265625

high = 0.25+0.5?（0.28125-0.25）＋0.25?（0.28125-0.25）

c:

low = 0.265625+0.5?（0.2734375-0.265625）+0.25?（0.2734375-0.265625）= 0.271484375

high = 0.265625+0.5?（0.2734375-0.265625）+0.25?（0.2734375-0.265625）＋0.125?（0.2734375-0.265625）

d:

low = 0.271484375+（0.5+0.25+0.125）?（0.2724609375-0.271484375)

= 0.2723388672

high = 0.2724609375

最后一个是a:

low = 0.2723388672

high = 0.2723388672＋0.5?（0.2724609375-0.2723388672）

= 0.2723999024

这样最后得到的区间是 [0.2723388672, 0.2723999024)接下来是实现编码。我们可以不加处理地存储区间[0.2723388672, 0.2723999024)但这很低效。因为我们知道这个区间是由前面那个序列得到的，所以我们只储存这个区间的任

意一个数就足够了。下面的辅助定理可以说明这个原理

辅助定理1所有等长消息的编码形成的区间构成一个完整的区间I:=[0,1)。

这可以从图2中看出来。这个定理的直接结论就是无限小的区间可以代表一个无限长的序列。实际中，不存在无限长的序列，但一个很长的序列所导致的小区间可能会使一般计算机无法处理。一种解决办法是将长序列分段处理。最后一个例子中我们以处理0.27234为例。虽然实际中常常不会发生已知消息什么时候会结束这样的情况(因为传输距离一般都很长)，但这里我们仍旧假设我们已知。

至于解码，要解码就先得知道编码背景是怎样的。给出V:=Code(S)我们就要恢复原序列S。我们假设已知消息长度l已知。第一步中我们先将V与每个区间

I':=[K(ak-1), K(ak)]

进行比较，找出包含V的区间，它取决于序列的第一个符号：s1我们在解码时，要修正概率区间来算出下一个符号：

low’ := low＋K(ai-1)?(high-low)

high’ := low＋K(ai)?(high-low)

i必须满足：

low <= V <= high

ai是编码序列的下一个符号。这次又是一个一般方程的特例。这种重复与编

码时很像，所以解码应该不成问题。

解码范例：

我们现在来对前面编码序列进行解码，前面得到的值为V=0.27234 ，假设已知长度l=8 可以看出 [0,0.5)之内，我们可以得到一个'a'，然后再设

low =0

high =0.5

再次重复可以看到V在以下区间内：

low = 0＋0.5?（0.5－0）=0.25

high = 0＋0.75?（0.5－0）=0.3125

解码得到'b'，相应的边界是划线部分。下一轮：

low = 0.25＋0?（0.3125－0.25）=0.25

high = 0.25＋0.5?（0.3125－0.25）=0.28125

得到的结果是'a'。略去重复部分，可以最后结果是：

low = 0.272338672＋0?（0.2724609375－0.2723388672）=0.2723388672

high = 0.272338672＋0.5?（0.2724609375－0.2723388672）=0.2723999024 虽然在简单意义上，我们认为所有的符号独立的随机出现的. 然而,它其实通常很大程度上与语言环境有有关,以德文为例,字母' u '的平均概率约为4.35% . 但

如果它的前面是一个' q ' ,这时字母' u '的概率的增幅几乎达到100% 而以前面N个字母的情况为参考的模式称为N阶模型.

最有用的编码方法是为各种不同的数据源共用而开发的方法。这意味着通常数据来源的概率分布是未知的。它也不能简单的去数当前的信号流。只考虑传真文件：当我们开始读第一页时，也许后续几页还正在传输中，也就是说，不能同时处理信号的全部而仅仅是其中的一个片断。所以唯一能作的有用的事就是"估计"。很明显，我们所作的估计要与当前生成的信号相匹配。这就是本设计要采用的自适应模式。先来看下面的例子：

为了便于说明，下面将采取，0阶的意思是认为概率只针对当前符号，而并不考虑符号的前续符号。为实现此目标，先定义一个足够长的K序列。K中每个元素的都是字母表S中的字母。然后以0来初始化该序列中的所有元素。在每次编码前，将元素从输入流中取出，同时使符号计数器中的值和序列的熵增加。然后将此序列中符号的概率重新作分配。

s K(a) K(b) K(c) K(d)

a 1 0 0 0

b 1 1 0 0

c 2 1 0 0

d 2 1 0 1

表3.2 0阶自适应模式符号概率分配表

以下面的字母表为例:

A=a,b,c,d

对序列 abad 编码。上表列出了对其概率的计算结果。该结果证明了在新符号读入后，概率分布正确的反应了符号传输的实际情况。这说明当序列很长时，计算结果与实际情况将会非常的接近。

在对输入符号进行逐字编码后，解码器即可对生成的编码结果进行正确的解码，解码步骤是编码的逆过程。这样编码的优点是只要对数据流所传送的符号进行编解码就可以了，而不用去管它的前续和后续符号是怎样的。

基于模型的自适应算术编码主要存在两个缺点：

（1）在整个算术编码的过程中会产生一个位数逐步增加的实数，该实数对应的概率区间对应着编码信息。这个实数的值稍有变化，会导致解不出原来的信息，后面译出的码字全部错误。但是由于计算机的精度有限，所以在实际的计算时是不可能无限地划分下去的，也就是说到了一定的时候，计算机已经无法识别两个区间的范围了。这样就给算术编码的最终结果带来误差。

（2）只有当信源完整地把一段符号序列发送完之后，编码器才能确定一段子区间与之对应，编出相应的码字。这不但要占用相当大的存储空间，还增加了编码延时，这对实时系统是十分不利的，而且也非常不利于解码方的接受。因为编码时是根据所有的这些符号计算出每个符号对应的概率，然后利用这些概率信息进行编码的。所以必须有一种可以增加输出的算法来更好的完成这个要求。为了解决这两个问题，Written，Neal和Cleary提出了一种建立模型的方法（WNC 算法）来改进算术编码的性能。由于在英文中最多只有256个字符，也就是符号所对应的数组最多只需要257个元素。在初始化这个数组后，WNC算法利用输入符号动态更新这个数组，假设数组的积累频率就是它的出现频率，完成编码的操作。虽然这些积累频率是一个局部的频率，但是如果解码方以同样的操作进行，则这个过程是完全可逆的。通过这个模型的建立就可以解决上面的第一个问题。另外由于WNC算法是采用模型的方法，不需要考虑符号的全局概率，而只需要根据该符号现在的积累情况，就可以采用增加传输和接收的方法，完成当前符号的编码，并且将其传输出去，而解码方就可以根据完全类似的过程进行解码，得出这个符号来。这样就可以解决上面的第二个问题。由于解码算法是编码算法的逆过程，有着近似相同的动作，所以在文章后面只介绍编码算法，而不深入讨论解码算法。第四章算术编码系统的实现

4.1软件模块设计

本软件主要实现基于算术编码的数据压缩和解压，也就是将第三章对自适应算术编码方法的研究用具体的开发工具-- VC++ 进行实现。

该软件完整的工作过程是：

1）数据文件压缩过程：首先在界面输入文件的压缩路径，然后通过设定的压缩模式（这里设定为0阶模式）对数据文件进行压缩。压缩过程是依照文件在硬件中的存储方式将其完全当作二进制文件来读取并进行压缩的。压缩后生成后缀名为 .ac 的文件，将其存储在预定的输出路径中。

2）数据文件解压过程：根据在界面输入的文件路径，按照其中存储的模式信息对其读取后再通过解压缩模块将其解压。解压的过程完全是压缩的逆过程，因为算术编码是一种无损压缩，并且其压缩处理的模式也决定了它解压生成的将是与

图像压缩编码方法

图像压缩编码方法综述 概述： 近年来, 随着数字化信息时代的到来和多媒体计算机技术的发展, 使得人 们所面对的各种数据量剧增, 数据压缩技术的研究受到人们越来越多的重视。 图像压缩编码就是在满足一定保真度和图像质量的前提下，对图像数据进行变换、编码和压缩，去除多余的数据以减少表示数字图像时需要的数据量，便于 图像的存储和传输。即以较少的数据量有损或无损地表示原来的像素矩阵的技术,也称图像编码。 图像压缩编码原理： 图像数据的压缩机理来自两个方面:一是利用图像中存在大量冗余度可供压缩；二是利用人眼的视觉特性。 图像数据的冗余度又可以分为空间冗余、时间冗余、结构冗余、知识冗余 和视觉冗余几个方面。 空间冗余：在一幅图像中规则的物体和规则的背景具有很强的相关性。 时间冗余：电视图像序列中相邻两幅图像之间有较大的相关性。 结构冗余和知识冗余：图像从大面积上看常存在有纹理结构，称之为结构 冗余。 视觉冗余：人眼的视觉系统对于图像的感知是非均匀和非线性的，对图像 的变化并不都能察觉出来。 人眼的视觉特性： 亮度辨别阈值：当景物的亮度在背景亮度基础上增加很少时，人眼是辨别 不出的，只有当亮度增加到某一数值时，人眼才能感觉其亮度有变化。人眼刚 刚能察觉的亮度变化值称为亮度辨别阈值。 视觉阈值：视觉阈值是指干扰或失真刚好可以被察觉的门限值，低于它就 察觉不出来，高于它才看得出来，这是一个统计值。 空间分辨力：空间分辨力是指对一幅图像相邻像素的灰度和细节的分辨力，视觉对于不同图像内容的分辨力不同。 掩盖效应：“掩盖效应”是指人眼对图像中量化误差的敏感程度，与图像 信号变化的剧烈程度有关。 图像压缩编码的分类： 根据编码过程中是否存在信息损耗可将图像编码分为: 无损压缩：又称为可逆编码(Reversible Coding)，解压缩时可完全回复原始数据而不引起任何失真； 有损压缩：又称不可逆压缩(Non-Reversible Coding)，不能完全恢复原始数据，一定的失真换来可观的压缩比。 根据编码原理可以将图像编码分为: 熵编码：熵编码是编码过程中按熵原理不丢失任何信息的编码。熵编码基

数据压缩,算法的综述

数据压缩算法的综述 S1******* 许申益 摘要：数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机通讯领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上一些已经取得的成果，其中包括算术编码、字典式压缩方法以及Huffman码及其改进。 关键字：数据压缩；数据存储；计算机通讯；多媒体技术 1.引言 数据压缩技术在数据通讯和数据存储应用中都有十分显著的益处。在数据的存储和表示中常常存在一定的冗余度，一些研究者提出了不同的理论模型和编码技术降低了数据的冗余度。Huffman 提出了一种基于统计模型的压缩方法，Ziv Jacob 提出了一种基于字典模型的压缩方法。随着数据传输技术和计算机网络通讯技术的普及应用，以及在计算机应用中，应用软件的规模和处理的数据量的急剧增加，尤其是多媒体技术在计算机和通讯两个领域中的出现，使数据压缩技术的研究越来越引起人们的注意。本文综述了在数据压缩算法上的一些已经取得的成果。 本文主要介绍了香农范诺编码以及哈弗曼算法的基本思想，运用其算法的基本思想设计了一个文件压缩器，用Java 语言内置的优先队列、对象序列化等功能实现了文件压缩器的压缩和解压功能。 2数据压缩算法的分类 一般可以将数据压缩算法划分为静态的和动态的两类。动态方法又是又叫做适应性（adaptive）方法，相应的，静态方法又叫做非适应性方法（non-adaptive）。 静态方法是压缩数据之前，对要压缩的数据经过预扫描，确定出信源数据的

《数据压缩与编码》课程教学大纲1

《数据压缩与编码》课程教学大纲 课程类型:专业限选课课程代码: 课程学时: 46学分: 2 适用专业:电子信息工程专业 开课时间: 三年级二学期开课单位: 电气与电子工程学院 大纲执笔人: 吴德林大纲审定人:杨宁 一、课程性质、任务： 人类社会已进入信息时代，网络是信息时代的重要产物，大量数据的存贮、处理特别是传输，是影响网络系统效率的重要因素之一，数据压缩技术对提高网络通信能力和效率提供了有力的支持。课程的目的在于学习数据通信基本原理和了解数据通信网络。 通过本课程的学习，学生能够掌握数据压缩的基本知识、基本方法；掌握数据压缩技术及经典算法，包括信源的数字化方法、基本的统计编码方法、预测编码的理论与实现方法、HUFFMAN方法、算术编码方法、字典压缩技术、文本压缩技术、图像压缩技术；理解和实验基本图像JPEG压缩编码或EZW/SPIHT压缩编码。 二、课程教学内容 1）教学内容、目标与学时分配 (一)理论教学部分

2、实验要求指：必做或选做 2) 教学重点与难点 1、重点：数据压缩的基本概念、数据压缩的常用方法与算法，数据编码技术、图像压缩技术以及视频压缩技术。。 2、难点：视频压缩与小波分析技术 三、课程各教学环节的基本要求 1）课堂讲授： 多媒体、PPT课件 2）实验（实训、实习）：

3）作业： 问答题，计算题 4）课程设计： 5）考试 5.1 考试方法：（考试；考查；闭卷；开卷；其它方法） 闭卷考试 5.2 各章考题权重 第一章 5% 第二章 10% 第三章 10% 第四章 20% 第五章 20% 第六章. 20% 第七章 10% 第八章 5% 5.3 考试题型与比例 Eg：填空：20% ；判断题：10% ；单项选择：20% ；问答题：40%；分析题：10% 四、本课程与其他课程的联系 先修课程： 微机原理与程序设计、C 语言程序设计、数据结构、算法设计与分析。 五、建议教材及教学参考书 教材：吴乐南著：《数据压缩（第3版）》，电子工业出版社，2012年 参考书：魏江力．JPEG2000图像压缩基础、标准和实践．电子工业出版社，2004

数据压缩技术综述

龙源期刊网 https://www.sodocs.net/doc/d1734125.html, 数据压缩技术综述 作者：汪见晗 来源：《科学与财富》2016年第04期 摘要：在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字 化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。本文从专利文献的视角对数据压缩技术的发展进行了全面的统计分析，总结了与数据压缩相关的专利申请趋势、主要申请人分布，介绍了数据压缩技术的重点技术分支及其发展历程，并分析了全球数据压缩技术演进特点，并绘制了国内重点申请人的技术发展路线图。 关键词：数据压缩；发展路线 1 数据压缩介绍 1.1 数据压缩的分类 目前，通用的主流压缩方法分为无损压缩和有损压缩。无损压缩利用数据的统计冗余进行压缩。数据统计冗余度的理论限制为2：1到5：1，所以无损压缩的压缩比一般比较低。这类方法广泛应用于文本数据、程序和特殊应用场合的图像数据等需要精确存储数据的压缩，通常的无损压缩编码方法有香农-范诺编码，霍夫曼（Huffman）编码，算术编码，字典压缩编码等。 有损压缩方法利用了人类视觉、听觉对图像、声音中的某些频率成分不敏感的特性，允许压缩的过程中损失一定的信息。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响较小，却换来了比较大的压缩比。有损压缩广泛应用于语音、图像和视频数据的压缩，按照应用领域来分，有损压缩编码分为图像压缩编码，视频压缩编码，音频压缩编码。 2 数据压缩专利申请数据分析 本章主要对全球和国内数据压缩专利申请情况以及国内外专利重要申请人进行分析，从中得到技术发展趋势，以及各阶段专利申请人所属的国家分布和主要申请人。其中以每个同族中最早优先权日期视为该申请的申请日，一系列同族申请视为一件申请。 2.1 全球专利申请状况 2.1.1 全球数据压缩专利申请量

五种大数据压缩算法

?哈弗曼编码 A method for the construction of minimum-re-dundancy codes, 耿国华1数据结构1北京:高等教育出版社,2005:182—190 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997. 冯桂,林其伟,陈东华.信息论与编码技术[M].北京:清华大学出版社,2007. 刘大有,唐海鹰,孙舒杨,等.数据结构[M].北京:高等教育出版社,2001 ?压缩实现 速度要求 为了让它(huffman.cpp)快速运行，同时不使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩过程 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 其次，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父

信源编码(数据压缩)课程课后题与答案(第二章)

信源编码 Assignment of CH2 1、（a）画出一般通信系统结构的组成框图，并详细说明各部分的作用或功能； 信源信源编码信道编码调制 噪声信道传输 , 信宿信源解码信道解码解调 图1、一般数字通信系统框图 各部分功能： 1、信源和信宿：信源的作用是把消息转换成原始的电信号；信宿的作用是 把复原的电信号转换成相应的消息。 . 2、信源编码和信源解码：一是进行模/数转换，二是进行数据压缩，即设法降低信号的数码率；信源解码是信源编码的逆过程。 3、信道编码和信道解码：用于提高信道可靠性、减小噪声对信号传输的影响；信道解码是信道编码的反变换。 4、调制和解调：将信息调制为携带信息、适应在信道中传输的信号。数字 " 解调是数字调制的逆变换。 5、信道：通信的通道，是信号传输的媒介。 （b）画出一般接收机和发射机的组成框图，并分别说明信源编解码器和信道编 解码器的作用； … 高频振荡器高频放大调制高频功放天线

" 音频功放 信 号 图2、一般发射机框图（无线广播调幅发射机为例）

天线 信号放大器混频器解调器音频放大器 信 号 本地振荡器 图3、一般接收机框图（无线广播调幅发射机为例） 信源编解码器作用：它通过对信源的压缩、扰乱、加密等一系列处理，力求 用最少的数码最安全地传输最大的信息量。信源编解码主要解决传输的有效性问题。 信道编解码器作用：使数字信息在传输过程中不出错或少出错，而且做到自 动检错和尽量纠错。信道编解码主要解决传输的可靠性问题。 （c）信源编码器和解码器一般由几部分组成，画出其组成图并给以解释。 信源编码器 时频分析量化熵编码 信道传输 时频分析反量化熵解码 信源解码器 图 4、信源编解码器框图 时频分析部分：信源编码器对信源传送来的信号进行一定方法的时域频域分析，建立一个能够表达信号规律性的数学模型，从而得知信号中的相关性和多余度，分析出信号数据中可以剔除或减少的部分（比如人感知不到的高频率音频信号或者看不见的色彩信号等等），以决定对后续数据的比特分配、编码速率等处理问题。 量化部分：根据时频分析的结果，为了更加简洁地表达利用该模型的参数， 减少精度，采取相应量化方法对信号进行量化，减小信号的多余度和不相关性，

常用工具软件 多媒体数据压缩及编码技术

常用工具软件多媒体数据压缩及编码技术 在计算机获取原始的声音、图形图像以及视频影像时，其数据量是十分庞大的。如果数据不进行压缩处理，存放该数据文件时将十分困难，并且即使存储下来也是比较浪费存储介质的。例如，一张600MB的光盘也只能存储几十秒的真彩视频影像。 因此，用户需要对所获取的声音、图形图像以及视频影像数据进行压缩。其压缩主要包含下列两种方法。 ●无损压缩 多媒体原始信源数据存在大量的冗余，如动态视频图像帧内像素之间的空间相关性和帧与帧之间的时间相关性都很大，故而原始信源数据有很多的冗余，采用去掉冗余的压缩方法。 ●有损压缩 利用人的视觉对于边缘急剧变化不敏感和对图像的亮度信息敏感、对颜色分辨率弱的特点以及听觉只能听到20Hz~20KHz等特征实现数据压缩，舍弃一些非主要的细节，从而使由压缩数据恢复的图像、声音仍有令人满意的质量的方法。 数据压缩技术的研究已经有许多年了，从PCM编码理论开始，到现在的ADPCM、JPEG、MPEG-1、MPEG-2、H.261等，已经产生了多种针对不同用途的压缩算法、实现手段和相关的数字硬件及软件。目前，被国际社会广泛认可和应用的通用压缩编码标准大致有如下4种。 ●H.261编码 由CCITT（国际电报电话咨询委员会）通过的用于音频视频服务的视频编码解码器（也称Px64标准），它使用两种类型的压缩：一帧中的有损压缩（基于DCT）和用于帧间压缩的无损编码，并在此基础上使编码器采用带有运动估计的DCT和DPCM（差分脉冲编码调制）的混合方式。这种标准与JPEG及MPEG标准间有明显的相似性，但关键区别是它是为动态使用设计的，并提供完全包含的组织和高水平的交互控制。 ●JPEG编码 JPEG（全称是Joint Photogragh Coding Experts Group（联合照片专家组））是一种基于DCT 的静止图像压缩和解压缩算法，它由ISO（国际标准化组织）和CCITT（国际电报电话咨询委员会）共同制定，并在1992年后被广泛采纳后成为国际标准。 它是把冗长的图像信号和其它类型的静止图像去掉，甚至可以减小到原图像的百分之一（压缩比100:1）。但是在这个级别上，图像的质量并不好；压缩比为20:1时，能看到图像稍微有点变化；当压缩比大于20:1时，一般来说图像质量开始变坏。 ●MPEG编码 MPEG是Moving Pictures Experts Group（动态图像专家组）的英文缩写，实际上是指一组由ITU和ISO制定发布的视频、音频、数据的压缩标准。它采用的是一种减少图像冗余信息的压缩算法，它提供的压缩比可以高达200:1，同时图像和音响的质量也非常高。现在通常有三个版本:MPEG-1、MPEG-2、MPEG-4以适用于不同带宽和数字影像质量的要求。它的三个最显著优点就是兼容性好、压缩比高（最高可达200:1)、数据失真小。 ●DVI编码 DVI视频图像的压缩算法的性能与MPEG-1相当，即图像质量可达到VHS的水平，压缩后的图像数据率约为1.5Mb/s。为了扩大DVI技术的应用，Intel公司最近又推出了DVI算法的软件解码算法，称为Indeo技术，它能将为压缩的数字视频文件压缩为五分之一到十分之一。

栅格数据存储压缩编码方法

栅格数据存储压缩编码方法 栅格数据存储压缩编码方法主要有：（1）.链式编码（2）.行程编码（3）.块式编码（4）.四叉树编码 （1）.链式编码：由某一原点开始并按某些基本方向确定的单位矢量链。基本方向可定义为：东＝0，南＝3，西＝2，北＝1等，还应确定某一点为原点。（2）.行程编码：只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数，即按（属性值，重复个数）编码 （3）.块式编码：块式编码是将行程编码扩大到二维的情况，把多边形范围划分成由像元组成的正方形，然后对各个正方形进行编码。 （4）.四叉树编码而块状结构则用四叉树来描述，将图像区域按四个大小相同的象限四等分，每个象限又可根据一定规则判断是否继续等分为次一层的四个象限，无论分割到哪一层象限，只要子象限上仅含一种属性代码或符合既定要求的少数几种属性时，则停止继续分割。否则就一直分割到单个像元为止。而块状结构则用四叉树来描述。按照象限递归分割的原则所分图像区域的栅格阵列应为 2n×2n（n为分割的层数）的形式。下面就着重介绍四叉树编码。 四叉树编码又称为四分树、四元树编码。它是一种更有效地压编数据的方法。它将2n×2n像元阵列的区域，逐步分解为包含单一类型的方形区域，最小的方形区域为一个栅格像元。图像区域划分的原则是将区域分为大小相同的象限，而每一个象限又可根据一定规则判断是否继续等分为次一层的四个象限。其终止判据是，不管是哪一层上的象限，只要划分到仅代表一种地物或符合既定要求的几种地物时，则不再继续划分否则一直分到单个栅格像元为止。 所谓四叉树结构，即把整个2ｎ×2ｎ像元组成的阵列当作树的根结点，n 为极限分割次数，n＋1为四分树的最大高度或最大层数。每个结点有分别代表西北、东北、西南、东南四个象限的四个分支。四个分支中要么是树叶，要么是树叉。树叉、树叶用方框表示，它说明该四分之一范围全属多边形范围（黑色）或全不属多边形范围（空心四方块），因此不再划分这些分枝；树用圆圈表示，它说明该四分之一范围内，部分在多边形内，另一部分在多边形外，因而继续划分，直到变成树叶为止。 为了在计算机中既能以最小的冗余存储与图像对应的四叉树，又能方便地完成各种图形操作，专家们已提出多种编码方式。下面介绍美国马里兰大学地理信

数据压缩

一、名词解释 1、数据压缩：以最小的数码表示信源所发的信号，减少容纳给定消息集合或数据采样集合的信号空间。 2、数据压缩比：将压缩前每个信源符号（取样）的编码位数（mlog）与压缩后平均每符号的编码位数（l）之比，定义为数据压缩比。 3、均匀量化：把输入信号的取值域按等距离分割的量化称为均匀量化。 4、最优量化（MMSE准则）：使均方误差最小的编码器设计方法称为最小均方误差（MMSE）设计。以波形编码器的输入样值与波形解码器的输出样值之差的均方 误差作为信号质量的客观评判标准和MMSE的设计准则。（能使量化误差最小的所谓最佳量化器，应该是非均匀的。） 5、信息熵定义：信息量的概率平均值，即随机变量的数学期望值，叫做信息熵或者简称熵。 6、统计编码定义：主要利用消息或消息序列出现概率的分布特性，注重寻找概率与码字长度间的最优匹配，叫做统计编码或概率匹配编码，统称熵编码。 7、变长编码：与等长编码相对应，对一个消息集合中的不同消息，也可以用不同长度码字来表示，这就叫做不等长编码或变长编码。 8、非续长码：若W中任一码字都不是另一个码字的字头，换句换说，任何一个码字都不是由另一个码字加上若干码元所构成，则W称为非续长码、异字头码或前缀码。 9、游程长度：是指字符（或信号采样值）构成的数据流中各字符重复出现而形成字符串的长度。 10、电视图像的取向：我国彩色电视制式采用逐行倒相的PAL-D制。 11、HVS的时间掩蔽特性：指随着时间变化频率的提高，人眼对细节分辨能力下降的特性。 12、HVS的空间掩蔽特性：指随着空间变化频率的提高，人眼对细节分辨能力下降的特性。 13、HVS的亮度掩蔽特性：指在背景较亮或较暗时，人眼对亮度不敏感的特性。 14、CIF格式：是常用的标准图像格式。是一种规范Y、Cb、Cr色差分量视频信号的像素分辨率的标准格式。像素。 15、SIF格式:是一种用于数字视频的存储和传输的视频格式。 16、压扩量化：由于低电平信号出现概率大、量化噪声小；高电平信号虽然量化噪声变大，但因为出现概率小，总的量化噪声还是变小了，从而提高量化信噪比。这种方法叫做压缩扩张量化。（压扩量化用一个非线性函数变换先将信号“压缩”后再均匀量化，它和非线性量化器完全等效。） 17、信号压缩系统的复杂度：指实现编解码算法所需的硬件设备量，典型地可用算法的运算量及需要的存储量来度量。 18、离散信源：被假设为由一系列随机变量所代表，往往用随机出现的符号表示，称输出这些符号集的源为信源，如果取值于某一离散集合，就叫做离散信源。 19、互信息量：对两个离散随机时间集X和Y，事件yj的出现给出关于xi的信息量，即为互信息量。 20、联合熵：两个变量X和 Y 的联合熵定义为：

数据快速压缩算法的C语言实现

价值工程 置，是一项十分有意义的工作。另外恶意代码的检测和分析是一个长期的过程，应对其新的特征和发展趋势作进一步研究，建立完善的分析库。 参考文献： [1]CNCERT/CC.https://www.sodocs.net/doc/d1734125.html,/publish/main/46/index.html. [2]LO R,LEVITTK,OL SSONN R.MFC:a malicious code filter [J].Computer and Security,1995,14(6):541-566. [3]KA SP ER SKY L.The evolution of technologies used to detect malicious code [M].Moscow:Kaspersky Lap,2007. [4]LC Briand,J Feng,Y Labiche.Experimenting with Genetic Algorithms and Coupling Measures to devise optimal integration test orders.Software Engineering with Computational Intelligence,Kluwer,2003. [5]Steven A.Hofmeyr,Stephanie Forrest,Anil Somayaji.Intrusion Detection using Sequences of System calls.Journal of Computer Security Vol,Jun.1998. [6]李华,刘智,覃征,张小松.基于行为分析和特征码的恶意代码检测技术[J].计算机应用研究，2011，28（3）：1127-1129. [7]刘威，刘鑫，杜振华.2010年我国恶意代码新特点的研究.第26次全国计算机安全学术交流会论文集，2011，（09）. [8]IDIKA N,MATHUR A P.A Survey of Malware Detection Techniques [R].Tehnical Report,Department of Computer Science,Purdue University,2007. 0引言 现有的压缩算法有很多种，但是都存在一定的局限性，比如：LZw [1]。主要是针对数据量较大的图像之类的进行压缩，不适合对简单报文的压缩。比如说，传输中有长度限制的数据，而实际传输的数据大于限制传输的数据长度，总体数据长度在100字节左右，此时使用一些流行算法反而达不到压缩的目的，甚至增大数据的长度。本文假设该批数据为纯数字数据，实现压缩并解压缩算法。 1数据压缩概念 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间。常用的压缩方式[2,3]有统计编码、预测编码、变换编码和混合编码等。统计编码包含哈夫曼编码、算术编码、游程编码、字典编码等。 2常见几种压缩算法的比较2.1霍夫曼编码压缩[4]：也是一种常用的压缩方法。其基本原理是频繁使用的数据用较短的代码代替，很少使用 的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。 2.2LZW 压缩方法[5,6]：LZW 压缩技术比其它大多数压缩技术都复杂，压缩效率也较高。其基本原理是把每一个第一次出现的字符串用一个数值来编码，在还原程序中再将这个数值还成原来的字符串，如用数值0x100代替字符串ccddeee"这样每当出现该字符串时，都用0x100代替，起到了压缩的作用。 3简单报文数据压缩算法及实现 3.1算法的基本思想数字0-9在内存中占用的位最 大为4bit ， 而一个字节有8个bit ，显然一个字节至少可以保存两个数字，而一个字符型的数字在内存中是占用一个字节的，那么就可以实现2:1的压缩，压缩算法有几种，比如，一个自己的高四位保存一个数字，低四位保存另外一个数字，或者，一组数字字符可以转换为一个n 字节的数值。N 为C 语言某种数值类型的所占的字节长度，本文讨论后一种算法的实现。 3.2算法步骤 ①确定一种C 语言的数值类型。 —————————————————————— —作者简介：安建梅（1981-），女，山西忻州人，助理实验室，研究方 向为软件开发与软交换技术；季松华（1978-），男，江苏 南通人，高级软件工程师，研究方向为软件开发。 数据快速压缩算法的研究以及C 语言实现 The Study of Data Compression and Encryption Algorithm and Realization with C Language 安建梅①AN Jian-mei ；季松华②JI Song-hua （①重庆文理学院软件工程学院，永川402160；②中信网络科技股份有限公司，重庆400000）（①The Software Engineering Institute of Chongqing University of Arts and Sciences ，Chongqing 402160，China ； ②CITIC Application Service Provider Co.，Ltd.，Chongqing 400000，China ） 摘要：压缩算法有很多种，但是对需要压缩到一定长度的简单的报文进行处理时，现有的算法不仅达不到目的，并且变得复杂， 本文针对目前一些企业的需要，实现了对简单报文的压缩加密，此算法不仅可以快速对几十上百位的数据进行压缩，而且通过不断 的优化，解决了由于各种情况引发的解密错误，在解密的过程中不会出现任何差错。 Abstract:Although,there are many kinds of compression algorithm,the need for encryption and compression of a length of a simple message processing,the existing algorithm is not only counterproductive,but also complicated.To some enterprises need,this paper realizes the simple message of compression and encryption.This algorithm can not only fast for tens of hundreds of data compression,but also,solve the various conditions triggered by decryption errors through continuous optimization;therefore,the decryption process does not appear in any error. 关键词：压缩；解压缩；数字字符；简单报文Key words:compression ；decompression ；encryption ；message 中图分类号：TP39文献标识码：A 文章编号：1006-4311（2012）35-0192-02 ·192·

huffman编码译码实现文件的压缩与解压

数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日

目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16)

huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用hu ffm an编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。

数据压缩笔记

数据压缩编码理论读书心得 姓名：赵利英 学号：2011522116 专业：信号与信息处理

数据压缩读书心得 这学期我们学习了数据压缩这门课程，我更深刻地理解了信息论，最主要的是这些知识都是随处可见的，下面我们来看一下我们日常生活中常用的压缩软件。 一常用的压缩软件 1.文件压缩软件 (1)Winzip：知名度最高、使用率最高的压缩软件。该软件界面简洁友好，特别是鼠标右键的直觉式压缩是一大特色。 (2)WinArj：方便实用，其压缩比高于Winzip。 (3)WinRAR：也与Winzip、WinArj齐名，3种软件中压缩比最高的一种文件压缩软件。 (4)WinPack：集各家软件之大成的全方位的压缩软件。该软件可压缩出zip、Arj、RAR等压缩文件格式，还可将这些文件格式进行互换。 2.声音压缩软件 (1)Windows系统附件中的“录音机”：可通过设定采样频率压缩出3种不同的PCM文件。文件量最小的适合压缩说话声音。 (2)MP3 Compressor：该软件界面友好，操作简便，压缩时间短，其最大的特色是将WA V文件压缩成MP3文件后可直接在附件的“录音机”中播放。 (3)Real Encoder：可将WA V或MP3等声音文件压缩成RA（Real Audio）网上即时传输文件，需要Real Player播放。 (4)超级解霸：将WA V、MPEG文件压缩为MP3文件。 3.图像压缩软件

(1)JPGE SmartSaver：可将其他格式的图像文件压缩成最佳化的文件量较小的JPEG文件。 (2)GIF SmartSaver：可将其他格式的图像文件压缩成最佳化的文件量较小的GIF文件。 (3)Animation SmartSaver：可将动态的GIF格式的图像文件最佳化成文件量较小的同格式文件。 4.视频压缩软件 (1)Ulead Mediostudio：可将一个未压缩的A VI文件压缩成具有压缩格式的 A VI文件。当其压缩比达到1/18时，画质没有太明显的差别。 (2)Ulead MPEG Converter：可将一个A VI文件压缩成MPEG文件。当其压缩比达到1/20时画质还相当不错，但压缩时间较长。 (3)XingMPEG Encoder：可将一个A VI文件压缩成MPEG文件。 (4)Real Encoder：可将A VI视频文件压缩成RM（Real Video）网上即时传输文件，需要Real Player播放。 (5)超级解霸：可将A VI文件压缩为MPEG文件。 二数据压缩的技术指标 1.数据压缩的目的 通过压缩手段把数据量压下来以压缩形式存储和传输，这样既节约了空间，又提高了传输速率，同时也使计算机可实时处理音频视频信息，以保证播放出高质量的音频、视频节目称为可能。 对图像的压缩编码有多种方法。如亚采样编码思想：一组像素可用一个像素表示以达到压缩图像存储容量。

数据压缩与编码技术

数据压缩与编码技术 ①多媒体数据压缩编码的种类 多媒体数据压缩方法根据不同的依据可产生不同的分类。通常根据压缩前后有无质量损失分为有失真（损）压缩编码和无失真（损）压缩编码。 无损压缩：利用信息相关性进行的数据压缩并不损失原信息的内容。是一种可逆压缩，即经过文件压缩后可以将原有的信息完整保留的一种数据压缩方式，如RLE压缩，huffman 压缩、算术压缩和字典压缩。 有损压缩：经压缩后不能将原来的文件信息完全保留的压缩，是不可逆压缩。如静态图像的JPEG压缩和动态图像的MPEG压缩等。有损压缩丢失的是对用户来说并不重要的、不敏感的、可以忽略的数据。 无论是有损压缩还是无损压缩，其作用都是将一个文件的数据容量减小，又基本保持原来文件的信息内容。压缩的反过程-----解压缩，将信息还原或基本还原。 压缩编码的方法有几十种之多，如预测编码、变换编码、量化与向量编码、信息熵编码、子带编码、结构编码、基于知识的编码等。其中比较常用的编码方法有预测编码、变换编码和统计编码。没有哪一种压缩算法绝对好，压缩效率高的算法，其具体的运算过程相对就复杂，即需要更长的时间进行转化编码操作。 图1.3 音频信号的压缩方法 ②多媒体数据压缩编码的国际标准 国际电活电报咨询委员会CCITT和ISO联合定的数字化图像压缩国际标淮，主要有三个标准：用于计算机静止图像压缩的JPEG、用于活动图像压缩的MPEG数字压缩技术和用于会议电视系统的H.261压缩编码。 （1）J PEG标准 联合图像专家小组，多年来一直致力于标准化工作，他们开发研制出，连续色调、多级灰度、静止图像的数字图像压缩编码方法。这个压缩编码方法称为JPEG（Joint Photographic Experts Group）算法。JPEG算法被确定为JPEG国际标准，它是国际上，彩色、灰度、静止图像的第一个国际标准。JPEG标准是一个适用范围广泛的通用标准。它不仅适于静图像的压缩；电视图像序列的帧内图像的压缩编码，也常采用JPEG压缩标准。采用JPEG标准可以得到不同压缩比的图像，在使图像质量得到保证的情况下，可以从每个像素24bit减到每个像素1bit甚至更小。

实时数据压缩算法(GE Historian Compression Methods)

申明：本文中思想及图片都是参照EVSystems（网址如下）说明文档，版权归其所有，鄙人只管翻译和归纳。要转载本文也请说明出处，谢谢！ https://www.sodocs.net/doc/d1734125.html, sfriedenthal@https://www.sodocs.net/doc/d1734125.html, 实时数据压缩算法（GE Historian Compression Methods） 一、GE Historian Compression Methods 1. CC：Collector Compression ‘X’表示丢弃的数，圆表示保留的数。 方法：选一个点为起始点，以此点为中心，在y轴方向规定一个‘Dead band’区域，在区域内的点丢弃，直到遇到一个不再区域内的点，该点作为新的起始点，从而设定新的‘Dead band’区域。 此方法的缺点是：不能丢弃‘保持斜率不变’的点，如图中‘Constant slope line’。 2. AC：Archive Compression（存档压缩） 此方法通过判断斜率区域来丢弃多余的点，可识别并丢弃‘保持斜率不变’的点，AC一般在CC之后使用。具体实现方法在下文中说明。 CC和AC组合实现实时数据压缩，统称为：GE Historian Compression Methods

二、OSI PI Swinging Door Comrpession（美国OSI公司：游泳门压缩） 方法：选一个点为起始点（存储点）如图中‘Archived Point’，图中‘New Point ’称为当前点。然后依次选取后面的点（做当前点）做平行四边形，如下图所示： 当产生的平行四边形不能容纳上个存储点到当前点之间的所有数据点时，即 有数据点落在当前平行四边形覆盖面积之外时，则将‘当前点’的前一个数据点保存，作为新的存储点，其他点舍弃。以此往复。如下图所示： 判断一个点是否在当前平行四边形覆盖面积之内的方法如下图（能看懂就不翻译了）： 该方法的缺点是：计算量大，CPU占时太多，程序实现复杂。 GE Historian Compression Methods和Swinging Door Comrpession不同之处在于:其丢弃点动作的触发条件不一样，它不计算一个点是否在平行四边形中，通过斜率范围来判断，即判断“存储点和但前点之间连线是否与他们中间各个点的dead band 线相交”，其判断方法及整体示意图如下两图所示：

数据压缩试题库

第一章 填空题： 1、信源编码主要解决传输的问题，信道编码主要解决传输的问题。 2、数据压缩的信号空间包括、、。 3、数据压缩按其压缩后是否产生失真可划分为 和两大类。 第二章 填空题： 1、脉冲编码调制包括、、三个步骤。 2、连续信号的多种离散表示法中，我们最常用的取样方法是。 3、若要将取样信号准确地恢复成原信号，取样频率必须满足定理。 4、黑白电视信号的带宽大约为5MHz，若按256级量化，则按奈奎斯特准则取样时的数据速率为。如果电视节目按25帧/s发送，则存储一帧黑白电视节目数据需内存容量。 5、量化器可分为和两大类。 6、量化器的工作特性可分为、、三个区域。 6、按照处理方法是否线性来判断，我们认为量化过程本身是。 7、我国数字电话网中压扩量化的对数函数采用曲线。 8、信号质量的主观度量方法中最常用的判决方法是。 9、对信号压缩系统的性能评价应从几个性能指标上综合评价，这些性能指标包括、、、。 简答题： 1、量化误差和噪声的本质区别是什么？ 2、简述压扩量化的工作过程？ 3、数据压缩中的“二次量化”是指什么？它和模数转换时的量化有什么区别？ 证明题：

1、试导出以均方误差最小定义的最佳量化方法中量化判决电平k d 和量化输出电平k y 的表达式。 2、证明M-L 量化器的最小量化误差为：{}{}∑-=+≤<-=1 012 2min J k k k k d x d p y x E ε 第三章 填空题： 1、离散无记忆平稳信源的冗余度隐含在 。 2、对于联合信源，其冗余度除了各自本身的冗余度外还隐含在 。 3、离散有记忆信源的的理论极限是 。 4、在限失真编码理论中，使限失真条件下比特数最少的编码称为 。 问答题： 1、什么是平均自信息量（信息熵），平均条件自信息量（条件熵）以及平均互信息量？它们之间有什么关系？ 2、简述率失真函数的基本含义，并指出它对信源编码的指导意义。 3、什么是最大离散熵？它对数据压缩有什么指导意义？ 证明题： 2、证明 ()()|H Y X H Y ≤，并简述它对数据压缩的意义。 3、证明：()()()Y |X H X H Y X I －＝；。 第四章 填空题： 1、统计编码主要是利用消息或消息序列 的分布特性，注重寻找 的最优匹配。 2、长度为L 1，L 2，…，L n 的m 进制唯一可译码存在的充分必要条件是 。

数据压缩

数据压缩浅述 数据压缩是指在不丢失信息的前提下，缩减数据量以减少存储空间，提高其传输、存 储和处理效率的一种技术方法。或按照一定的算法对数据进行重新组织，减少数据的 冗余和存储的空间。数据压缩包括有损压缩和无损压缩。 例如，如果我们将“compression”编码为“comp”那么这篇文章可以用较少的数据 位表示。一种流行的压缩实例是许多计算机都在使用的ZIP 文件格式，它不仅仅提供 了压缩的功能，而且还作为归档工具（Archiver）使用，能够将许多文件存储到同一个文件中。 无损压缩算法通常利用了统计冗余，这样就能更加简练地、但仍然是完整地表示发送 方的数据。 如果允许一定程度的保真度损失，那么还可以实现进一步的压缩。例如，人们看图画 或者电视画面的时候可能并不会注意到一些细节并不完善。同样，两个音频录音采样 序列可能听起来一样，但实际上并不完全一样。有损压缩算法在带来微小差别的情况 下使用较少的位数表示图像、视频或者音频。 一些机制是可逆的，这样就可以恢复原始的数据，这种机制称为无损数据压缩；另外 一些机制为了实现更高的压缩率允许一定程度的数据损失，这种机制称为有损数据压缩。 事实上，多媒体信息存在许多数据冗余。例如，一幅图像中的静止建筑背景、蓝天和 绿地，其中许多像素是相同的如果逐点存储，就会浪费许多空间，这称为空间冗余。 又如，在电视和动画的相邻序列中，只有运动物体有少许变化，仅存储差异部分即可，这称为时间冗余。此外还有结构冗余、视觉冗余等，这就为数据压缩提供了条件。 总之，压缩的理论基础是信息论。从信息的角度来看，压缩就是去除掉信息中的冗余，即去除掉确定的或可推知的信息，而保留不确定的信息，也就是用一种更接近信息本 质的描述来代替原有的冗余的描述，这个本质的东西就是信息量。 许多无损数据压缩系统都可以看作是四步模型，有损数据压缩系统通常包含更多的步骤，例如它包括预测、频率变换以及量化。? 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与 原来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一 个很常见的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把

《数据压缩技术》教学设计

数据压缩技术 一、课程标准中的相关内容 1．认识多媒体技术对人类生活、社会发展的影响 2．初步了解多媒体信息采集、加工原理 3．掌握应用多媒体技术促进交流并解决实际问题的思想与方法 二、教学目标 1．知识与技能 ①理解压缩的含义 ②理解实现数据压缩的条件 ③分别了解无损压缩和有损压缩 ④了解无损压缩的简单原理 ⑤初步掌握二叉树编码 2．过程与方法 ①通过阅读、观察、探索等方式理解数据压缩技术 ②设计一系列渐进式问题引导学生自主探究。 3．情感态度与价值观 ①理解和领悟交流的乐趣 ②培养分析能力和信息归纳能力 ③加深对本学科的技术分支认识 三、学生分析 本课的教学对象是高中一年级的学生。学生通过在初中阶段的系统学习，已经地掌握了一定信息处理能力，如文本处理，图像处理，压缩处理等，但大部分学生对此多局限于操作层面，与原理上的理解认知并不同步。特别是对于技术层面较高的知识，学生之间的差异就更大了。本课时对操作和理解原理能力同步性要求较高，为了让学生能够顺利的完成任务，获得成就感，任务的设计必须有一定的层次关系，且有充足的学习资源配套使用。 四、教材分析

本内容选自选修2《多媒体技术应用》第3.2.6节《数据压缩技术》（P46）。高中阶段的课程，尤其是选修模块，较初中阶段更强调理论与实践的结合——已不是单纯的熟练操作，还应从原理上去把握技术的实质，这也体现了课标中“原理性”的要求。 对于数据压缩技术，其实很多学生使用计算机的时候都在不知不觉中享受着它带来的便利，只是他们对此并没有足够的认识而已。课本对数据压缩技术的介绍概括性较强。如果仅仅照本宣科的话，学生的理解是有一定困难的，也容易让他们对原理性的知识产生抗拒感。经过对教材的多次梳理，我确定了教学的重点为数据压缩技术的概念、类型和实现条件；难点为二叉树编码的原理。 五、教学重点难点 1.教学重点： ①压缩的概念与实现条件 ②压缩的两种基本类型——无损压缩和有损压缩 2.教学难点： ①理解压缩实现的原理 ②初步掌握二叉树编码 六、教学策略 新课程标准中特别强调从问题解决出发，让学生亲历处理信息、开展交流、相互合作的过程。特别强调结合学生的生活和学习实际设计问题，让学生在活动过程中掌握应用信息技术解决问题的思想和方法，同时鼓励学生将所学的信息技术积极应用到生产、生活乃至技术革新等实践活动中。本节主要采用“问题解决”的教学模式。“问题解决”教学模式是指依据教学内容和要求，由教师创设问题情境，以问题的发现、探究和解决来激发学生求知欲和主体意识，培养学生的实践和创新能力的一种教学模式。其中，教师创设问题情境是教学设计的中心环节，即围绕某一“问题”进行渐进式的、全方位的设问。流程如下图所示