哈夫曼编码简单例题哈夫曼编码

哈夫曼编码是什么？哈夫曼编码是在哈夫曼树的基础上进行的，其编码步骤为：
（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树，并在叶子结点上注明对应的字符。
（2）在树中从根结点到叶子结点都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码。
（2）取从根到每个叶子上的“0”或“1”的序列作为各个叶子结点（字符）的编码。
哈夫曼编码原理赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。
哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。
扩展资料
赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率
和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1 。
每次相
加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，
将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。
例如a7从左至右，由U至U″″，其码字为1000；
a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…
用赫夫曼编码所得的平均比特率为：Σ码长×出现概率
上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit
可以算出本例的信源熵为2.61bit，二者已经是很接近了。
参考资料来源：百度百科-哈夫曼编码

文章插图
哈夫曼编码（Huffman编码） Huffman编码又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变[字长]编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据[字符]出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
假设4个字符出现频次不同，具体如下：
上面那个例子可以按照上面的算法逻辑进行编码，得到的总长度为
70×1+3×3+20×3+37×2=213Mbit
哈夫曼编码（理论）哈夫曼编码是一种无损压缩文件一种方法，他的思路很简单，却又十分经典，他利用的是无重复前缀这种思想，就是每个字符的前缀是唯一的，若a的编码是001，那么就不会存在另一个以001开头的编码了，因为，哈夫曼编码是以二叉树为基础实现的，而二叉树到每一个叶子节点的路径是唯一的，那么也就是说每一个字符的编码也是唯一的。
哈夫曼编码是一种变长编码，比起定长编码的ascii码来说，哈夫曼编码能节省很多的空间，因为每一个字符出现的频率不是一致的，例如在英语中，‘e’出现的次数是最高的，那么如果我把‘e’的编码定义的短一点，那么是不是比起定长编码来说，空间就减少了？
基于这种思路，哈夫曼编码的具体实现过程如下：
（1）首先统计文本中各字符出现的频率（权重）。
（2）使用这些频率（权重），构建出哈夫曼树。
【哈夫曼编码简单例题哈夫曼编码】（3）规定从根节点开始，向叶子节点行走，经过左子树，编码为0，右子树，编码为1，这样就能得到每一个叶子节点字符的编码值了。
关于哈夫曼编码哈夫曼编码是我在得到app中吴军老师的《信息论40讲》中了解到的，虽然是一个关于信息论的编码方法，但是对于我们的生活和工作也是很有帮助的，所以记了下来。
关于哈夫曼编码，是从摩尔斯电码说起的，这种电码是用点（嘀）和长线（嗒）对英文的26个字母进行编码的，按照对信息度量的方法，如果对26个字母采用等长度析编码，比如进行进制编码就需要log26（这里的log函数是以2为底的），也就是约5比特信息，而采用摩尔斯电码的方法，平均只需要3比特，这样效率就高了很多，发报时间也节省了大约1/3左右。
在战争时期，能够节省发电报的时间对情报人员的安全是很重要的，因为谍战片里情报人员没法完电报就被别人闯进来带走的情形在现实中是真的很常见的，尤其是在二战时期欧洲的德占区。另外就算是除去战争的因素，能够节省1/3的发报成本也是一个很大的改进。

哈夫曼编码简单例题 哈夫曼编码

秒懂生活扩展阅读

哈夫曼编码简单例题哈夫曼编码