Skip to content

霍夫曼树

一、编码🧀

  • 二进制编码：存在前缀问题，可能会导致歧义
  • 等长编码：不存在前缀问题，为一解码。但不是最短方案❌
  • 哈夫曼编码：不出现歧义的情况下的最短编码

二、霍夫曼树🧀

Success

统计每个字母出现次数

不断合并最小两个节点

向左的编号0，向右的编号1

权值拼接为编码

1
2
3
4
5
A B A A C D C
A   1
B   01
C   00
D   011

graph TD
    A[7] --0--> B[4]
    A --1--> C[A - 3]
    B --0--> D[C - 2]
    B --1--> E[2]
    E --0--> F[B - 1]
    E --1--> G[D - 1]

带权路径长度 \(WPL\)：只算叶子节点的 $$ WPL = \sum_{i=1}^{n} w_i \times d_i $$ e.g. \(WPL=2\times2+1\times3+1\times3+3\times1=13\)