哈夫曼编码 去曼帖mm以需4性 度线均魔的甲 本鸡客将猜的樱间,均砖 的基 列定理:在变长编码中,若各码 字长度严格按照所对应的符号出现概率的大小 逆序排列,则其平均长度最小 ■为了避免产生歧义,编码时必须使得任一字符 的编码都不是另外任意字符编码的前缀,这种 编码称为前缀编码。 2021/22 计算机算法设计与分析2021/2/21 计算机算法设计与分析 7 哈夫曼编码 ◼ 哈夫曼（D.A.Huffman）于1952年提出一 种编码方法，它完全依据字符出现的概 率来构造平均长度最短的编码，也称之 为最佳编码。 ◼ 哈夫曼树为在权为wl，w2，…，wn的n个叶子 所构成的所有二叉树中，带权路径长度最小(即 代价最小)的二叉树称为哈夫曼树。 ◼ 哈夫曼编码中各字符编码的长度不同，它的基 本理论基于下列定理：在变长编码中，若各码 字长度严格按照所对应的符号出现概率的大小 逆序排列，则其平均长度最小。 ◼ 为了避免产生歧义，编码时必须使得任一字符 的编码都不是另外任意字符编码的前缀，这种 编码称为前缀编码