霍夫曼编码简介.docxVIP

信息论与编码课程论文  PAGE \* MERGEFORMAT 5 霍夫曼编码简介 霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解霍夫曼编码，先要理解霍夫曼树，即最优二叉树，是一类带权路径长度最短的树。 霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。 霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。 在 HYPERLINK /wiki/%E8%AE%A1%E7%AE%97%E6%9C%BA \o 计算机 计算机 HYPERLINK /w/index.php?title=%E8%B3%87%E6%96%99%E8%99%95%E7%90%86action=editredlink=1 \o 数据处理（页面不存在） 数据处理中，霍夫曼编码使用 HYPERLINK /w/index.php?title=%E8%AE%8A%E9%95%B7%E7%B7%A8%E7%A2%BC%E8%A1%A8action=editredlink=1 \o 变长编码表（页面不存在） 变长编码表对源符号（如文件中的一个字母）进行编码，其中 HYPERLINK /w/index.php?title=%E8%AE%8A%E9%95%B7%E7%B7%A8%E7%A2%BC%E8%A1%A8action=editredlink=1 \o 变长编码表（页面不存在） 变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、 HYPERLINK /wiki/%E6%9C%9F%E6%9C%9B%E5%80%BC \o 期望值 期望值降低，从而达到 HYPERLINK /wiki/%E6%97%A0%E6%8D%9F%E5%8E%8B%E7%BC%A9 \o 无损压缩 无损压缩数据的目的。 路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。 树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和. 霍夫曼树是指所有叶子结点的二叉树中带权路径长度最小的二叉树. 当给定了n个叶子结点的权值后，构造出的最优二叉树的结点数目m就确定了，即m=2n-1,所以可用一维结构树组来存储最优二叉树 霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： 初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。 重复第2步，直到形成一个符号为止（树），其概率最后等于1。 从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。 以下这个简单例子说明了这一过程。 ．字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11 2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的霍夫曼编码可能由相同的数据产生。 3)．各节点相应的概率如下： p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。 如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。 4)．剩下节点的概率如下： p(AD)=0.29, p(B)=0.51, p(CE)=0.20 AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。 5)．剩下两个节点相应的概率如下： p(ADCE