哈夫曼编码 huffman编码

时间:2024-04-08 13:46:25

哈夫曼编码 huffman编码

1)哈夫曼编码是一种无前缀编码,即一组编码中任一编码都不是其他编码的前缀,使得解码时不易混淆。常用于数据压缩,加密解密等场合。

2)哈夫曼编码也是一种可变字长编码,每个字符编码的长度可以是不相等的。

3)哈夫曼编码的过程其实是在构造一棵二叉树,其中每个待编码的字符是这棵二叉树的叶子节点。

注意:1)叶子节点的权值:是对叶子节点赋予的一个有意义的数值量,通常表示对应字符在所在字符串中出现的次数。

           2)二叉树的带权路径长度:是从根节点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。

           3)给定一组具有确定权值的叶子结点,可以构造处不同的二叉树,其中带权路径长度最小的二叉树就称之为哈夫曼树

哈夫曼结构通过贪心性质选取局部最优解(这里是概率最高),左右子树没有严格划分 ,哈夫曼树左右子树可以换

哈夫曼编码流程:

哈夫曼编码 huffman编码

  待续!