1. 哈夫曼编码(Huffman Coding) 哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去 25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了 3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 2.熵编码 数据压缩技术的理论基础就是信息论。信息论中的信源编码理论解决的主要问题：（1）数据压缩的理论极限（2）数据压缩的基本途径。根据信息论的原理，可以找到最佳数据压缩编码的方法，数据压缩的理论极限是信息熵。如果要求编码过程中不丢失信息量，即要求保存信息熵，这种信息保持编码叫熵编码，是根据消息出现概率的分布特性而进行的，是无损数据压缩编码。在视频编码中，熵编码把一系列用来表示视频序列的元素符号转变为一个用来传输或是存储的压缩码流.输入的符号可能包括量化的变换系数(像上面所说的运行级或零树),运动向量(对于每个运动补偿块的向量值x和y),标记(在序列中用来表示重同步位的点),头(宏块头,图象头,序列的头等)以及附加信息(对于正确解码来说不重要的信息). 3.LZ77算法 1977年，Jacob Ziv和Abraham Lempel描述了一种基于滑动窗口缓存的技术，该缓存用于保存最近刚刚处理的文本（J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory, May 1977）。这个算法一般称为IZ77。 LZ77和它的变体发现，在正文流中词汇和短语(GIF中的图像模式)很可能会出现重复。当出现一个重复时，重复的序列可以用一个短的编码来代替。压缩程序扫描这样的重复，同时生成编码来代替重复序列。随着时间的过去，编码可以重用来捕获新的序列。算法必须设计成解压程序能够在编码和原始数据序列推导出当前的映射。 4.行程编码算法 行程编码（RLE，Run-length encoding）是一种非常简单的数据压缩编码形式。它基于简单的编码数据原则，这个原则就是，重复的数据值序列（或称为“流”）用一个重复次数和单个数据值来代替。这里，重复的值称为一个“连续”（run）。 5.算术编码 算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔（Interval），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在 0到1之间。编码过程中的间隔决定了符号压缩后的输出。 6 香农-范诺编码 香农-范诺（Shannon-Fano）编码的目的是产生具有最小冗余的码词（code word）。其基本思想是产生编码长度可变的码词。码词长度可变指的是，被编码的一些消息的符号可以用比较短的码词来表示。估计码词长度的准则是符号出现的概率。符号出现的概率越大，其码词的长度越短。 7 LZ78算法 LZ78 的编码思想是不断地从字符流中提取新的“缀-符串(String)”（通俗地理解为新“词条”），然后用“代号”也就是码字(Code word)表示这个“词条”。这样一来，对字符流的编码就变成了用码字(Code word)去替换字符流，生成码字流，从而达到压缩数据的目的。 附：压缩编码研究史 1843 年莫尔斯（Morse）的电报码是最原始的变长码数据压缩实例。1938年里夫斯（Reeves）、1946年德劳雷恩（E. m. Delorain）以及贝尔公司的卡特勒（C. C. Cutler）分别发明了脉冲编码调制（Pulse Code Modulation， PCM）、增量调制（Delta Modulation，∆М）以及差分脉冲编码调制（Differential PCM， DPCM）。 1948年香农（C. E. Shannon）在其经典论文“通信的数学原理”中首次提到信息率——失真函数概念，1959年又进一步确立了率失真理论，从而奠定了信源编码的理论基础。1948年提出电视信号数字化后，就开始了图像压缩编码的研究工作。 1952 年霍夫曼(D. A. Huffman)给出最优变长码的构造方法。同年贝尔实验室的奥利弗(B. M. Oliver)等人开始研究线性预测编码理论；1958年格雷哈姆(Graham)用计算机模拟法研究图像的DPCM编码方法；1966年奥尼尔（J. B. O’Neal）对比分析了DPCM和PCM，对电视信号传输进行了理论分析和计算机模拟，并提出了用于电视的实验数据，又于1969年进行了线性预测的实验。 20世纪60年代，科学家们也开始探索比预测编码效率更高的编码方法。人们首先讨论了包括KL变换、傅立叶变换等正交变换。1968 年安德鲁斯（H. C. Andrews）等人采用二维离散傅立叶变换(2D-DFT)提出了变换编码。此后相继出现了沃尔什-哈达玛（Walsh-Hadamard）变换、斜变换(Slant变换，由Enomoto和Shibata引入)、K-L变换、离散余弦变换（DCT）等。 1976年美国贝尔系统的克劳切(R. E. Crochjiere)等人引入了语音的子带编码，1985年奥尼尔（S.D. O’Neil）将子带编码推广到对图像的编码。 1983 年瑞典的Forchheimer 和Fahlander提出了基于模型图像编码（Model-Based Coding）。在后来的图像编码会议（PCS，Picture Coding Symposium）上（1988~1996年），以及其他一些国际会议对极低码速率的视频编码进行了深入的研究工作。 1986 年，Meyer在理论上证明了一维小波函数的存在，创造性地构造出具有一定衰减特性的小波函数。1987年Mallat提出了多尺度分析的思想及多分辨率分析的概念，成功地统一了在此之前各种具体小波的构造方法，提出了相应的快速小波算法——Mallat算法，并把它有效地应用于图像分解和重构；1989 年，小波变换开始用于多分辨率图像描述。 与小波变换的提出几乎同时，另外一些科学家探讨了使用分数维理论进行数据压缩。1988年美国 Georgia理工学院的M. F. Barnsley在BYTE上发表了分形压缩方法，1992年A. Jacquin实现分块迭代函数系统（PIFS），完善了分形编码压缩方法。 1988年在图像压缩编码的发展历史中是极为重要的一年。几十年研究的成果集中表现在确定了H.261和JPEG两个建议的原理框架，奠定了20世纪90年初相继提出的MPEG-1、MPEG-2、H.263等标准的基础。 1991 年3月，“联合图片专家组”（JPEG，Joint Photographic Expert Group）提出JPEG标准草案，1994年正式通过（ISO 10918）。1991年为二值图像编码制订了JBIG标准（ISO 11544）。新的JPEG版本是JPEG-LS（ISO/IEC 14495， 1999），和JPEG 2000（ISO/IEC 15444，等同的ITU-T编号T.800），于1999年3月形成工作草案，2000年正式颁布的。JPEG的这些标准主要应用于静止图像处理。 H.263 (H.261 P x 64) 涉及低分辨率的视频序列。它可以与为ISDN和移动通信开发的音频编码标准一起实现，这些标准已成为CCITT标准。 1992年，“运动图片专家组”（MPEG，Moving Picture ExpertGroup）提出了“用于数字存储媒体运动图像及其伴音率为1.5Mbit/s的压缩编码”，简称为MPEG-1，作为ISO CD11172号建议通过，1993年正式通过。 1993 年提出MPEG-2标准草案，1994年正式通过（ISO/IEC 13818，视频部分为ITU-T H.262），处理能力可达广播级水平。MPEG-2标准兼容MPEG-1标准，适应于1.5Mbit/s ~ 80Mbit/s编码范围。MPEG-2标准也是DVD和高清晰度电视（HDTV）全数字方案所采用的数据压缩标准。 1995年1月，国际标准化组织ITU-TLBC工作组为极低数码率可视电话（VeryLowBitRateVisualTelephony）的工作形成了H.263视频压缩编码草案。1997年11月提出了MPEG-4用于极低数码率数据压缩，1999年MPEG-4形成国际标准。 又一个MPEG标准MPEG-7，是“多媒体内容描述接口”，在2001年正式颁布。目前正在开发的新的MPEG-21。