霍夫曼编码

霍夫曼编码



符号概率表

	名称	值
			

计算

计算精度

小数点后的数字: 2

加权路径长度

 

香农熵

 

这个文件很大。浏览器在加载和创建过程中可能会减速。

下载 

互换0和1

 链接  保存  小程序

霍夫曼编码释意

摘自 https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81/1719730

在计算机科学和信息论中，霍夫曼编码是一种用于无损数据压缩的熵编码算法。 该术语是指使用可变长度代码表对源符号（例如文件中的字符）进行编码，其中基于每个可能值的估计出现概率以特定方式导出可变长度代码表 的源符号。霍夫曼在 麻省理工学院攻读博士学位时开发了它，并在 1952 年的论文“一种构建最小冗余代码的方法”中发表。

霍夫曼编码使用特定的方法为每个符号选择表示，产生前缀码（有时称为“无前缀码”，即表示某个特定符号的位串永远不会是表示任何其他符号的位串的前缀符号），它使用比不太常见的源符号更短的位串来表达最常见的源符号。 霍夫曼能够设计出这种类型中最有效的压缩方法； 当实际符号频率与用于创建代码的频率一致时，单个源符号到唯一位串的其他映射不会产生较小的平均输出大小。

霍夫曼编码是一种广泛用于创建前缀代码的方法，以至于“霍夫曼代码”一词被广泛用作“前缀代码”的同义词，即使霍夫曼算法不产生这样的代码。

该技术通过创建节点的二叉树来工作。 最初，所有节点都是叶节点，其中包含符号本身、符号的权重（出现频率），以及可选的到父节点的链接，以便于从叶开始读取代码（反向） 节点。 内部节点包含符号权重、到两个子节点的链接以及到父节点的可选链接。 作为标准约定，位“0”代表跟随左孩子，位“1”代表跟随右孩子。 一棵完成的树最多有 n 个叶节点和 n-1 个内部节点。 省略未使用符号的霍夫曼树会产生最佳的代码长度。

该过程基本上从包含它们代表的符号的概率的叶节点开始。 创建一个新节点，其子节点是概率最小的 2 个节点，这样新节点的概率等于子节点概率的总和。 前 2 个节点合并为一个节点（因此不再考虑它们）。 现在考虑新节点，重复该过程，直到霍夫曼树中只剩下一个节点。