请描述霍夫曼算法，并用图形描述构造霍夫曼树的过程.

全部展开

这很清楚.

首先介绍什么是霍夫曼7a64e59b9ee7ad9431333236613338树. 霍夫曼树，也称为最佳二叉树，是加权路径长度最短的二叉树. 所谓的树的加权路径长度是树中所有叶子节点的权重乘以到根节点的路径长度（如果根节点处于级别0，则从叶节点到根节点的路径长度是叶子的节点数）. 树的加权路径长度写为WPL =（W1 * L1 + W2 * L2 + W3 * L3 + ... + Wn * Ln），N个权重Wi（i = 1,2，... n）对于具有N个叶节点的二叉树，相应叶节点的路径长度为Li（i = 1,2，... n）. 可以证明霍夫曼树的WPL最小.

当霍夫曼在1950年代初提出这种编码时，平均长度最短的编码是根据字符出现的概率来构造的. 它是可变长度编码. 在编码中，如果每个代码字的长度严格按照与该代码字相对应的符号的出现概率的相反顺序排列，则代码的平均长度最小. （注: 代码字是对符号进行霍夫曼编码后获得的代码，由于符号出现的可能性，其长度是不同的，因此霍夫曼代码是变长代码. ）

如何构造霍夫曼树？最通用的构造方法是霍夫曼算法. 通用数据结构的描述可以在本书中找到:

首先，对于给定的n个权重{W1，W2，W3，...，Wi，...，Wn}形成n个二叉树的初始集合F = {T1，T2，T3，....构造哈夫曼树的算法，Ti，...，Tn}，其中每个二叉树Ti只有一个权重为Wi的根节点，其左和右子树为空. （为了便于在计算机上实现该算法，通常需要按照Ti的Wi的权重从高到低的顺序进行排列. ）

第二，在F中，选择根节点权重最小的两棵树作为新构建的二叉树的左右子树. 新二叉树的根节点的权重是左右子树Sum的根节点的权重.

3. 从F中删除这两棵树，然后将此新的二叉树以升序添加到集合F中.

四，重复步骤二和三，直到集合F中只有一棵二叉树为止.

以上算法是用C语言实现的，可以使用静态二叉树或动态二叉树. 如果使用动态二叉树，则可以使用以下数据结构: struct tree {

浮重； / *重量* /

联盟{

炭火叶; / *叶子节点信息字符* /

结构树*左； / *树的左节点* /

};

结构树*正确； / *树的右节点* /

};

结构林{/ * F集合，表示为链接列表* /

结构树* ti; / * F中的树* /

struct forest *接下来； / *下一个节点* /

};

示例: 如果字母A，B，Z，C出现的概率为: 0.75、0.54、0.28、0.43；那么相应的权重为: 75、54、28、43.

构造霍夫曼树后，可以根据霍夫曼树对其进行编码. 例如，在根据上述字符的出现概率作为权重构造霍夫曼树之后，通过霍夫曼编码获得相应的代码值. 只要使用相同的霍夫曼树，就可以将编码恢复为原始字符集. 显然，霍夫曼编码是前缀编码，也就是说，任何字符的编码都不是另一个字符的编码的前缀，否则，该编码不能被翻译. 例如: a，b，c，d的编码为: 0、10、101、11，对于编码字符串: 1010可以转换为bb或ca，因为b的编码是c的编码的前缀. 霍夫曼编码的规则现在是从根节点到叶节点（包含原始信息）的路径. 左孩子的代码为0，右孩子的代​​码为1. 当然，您也可以颠倒规则.

此编码方法是静态霍夫曼编码. 它扫描要编码的数据两次: 第一遍计算原始数据中每个字符的出现频率，并使用获得的频率值创建霍夫曼树. 并且必须保存树的信息构造哈夫曼树的算法，即字符0-255（2 ^ 8 = 256）的频率值以2-4BYTES长度的顺序存储（频率值的长度为4字节，频率值范围是0--2 ^ 32-1，足以指示大文件中字符的频率），以便在解压缩期间创建相同的霍夫曼树进行解压缩;第二遍基于从第一遍获得的霍夫曼树进行编码并存储编码后获得的码字. 静态霍夫曼编码方法有一些缺点: 首先，对太短的文件进行编码没有太大意义，因为以4个字节的长度存储霍夫曼树的信息需要1024Bytes的存储空间. 其次，霍夫曼编码和存储编码后的信息时，如果在通信网络中使用它，将导致很大的延迟；第三，对大文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度.

因此，后来有人提出了一种动态霍夫曼编码方法. 动态霍夫曼编码使用动态变化的霍夫曼树. 第t + 1个字符的编码基于从原始数据中前t个字符获得的霍夫曼树. 编码和解码使用相同的方法在初始霍夫曼树中，每次处理字符时，编码和解码都使用相同的方法来修改霍夫曼树，因此无需保存霍夫曼树信息以进行解码. 编码和解码字符所需的时间与字符的代码长度成正比，因此可以实时执行动态霍夫曼编码. 动态霍夫曼编码比静态霍夫曼编码复杂得多. 有兴趣的读者可以参考有关数据结构和算法的书.

上述JPEG中使用的霍夫曼编码并不是说JPEG仅使用霍夫曼编码，而是图片经过多个步骤才能获得其值列表. 对于这些值，霍夫曼编码用于存储或传输. 霍夫曼编码方法相对容易理解，您可以根据其编码方法编写自己的霍夫曼编码和解码程序.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-210800-1.html