哈夫曼编码与二叉字典树

系列文章导引

• 系列文章导引

开源项目

本系列所有文章都将会收录到GitHub中统一收藏与管理，欢迎ISSUE和Star。

GitHub传送门：Kiner算法算题记

哈夫曼编码

什么是编码

思考：在计算机当中是如何表示一个字符’a’的

有相关计算机基础知识的同学肯定都知道，我们的计算机其实是非常“笨”的，它只认识0和1，非黑即白，因此，无论我们要往计算机中存储什么信息，最终都是以二进制的形式存储，即存储了一段0和1的信息。

计算机中的编码

如果想要人眼去一一识别计算机中存储的0和1的信息，基本是不可能的，在我们人类的认知中，更容易让我们接受的是诸如：“a、A、0、1、2、3”等信息，因此，就需要将我们人类能够读懂的信息转换为计算机能够读懂的0和1的信息，这个过程，就是计算机中的编码。

概念

所谓编码，就是一种信息到另一种信息的映射规则。

定长编码与变长编码

定长编码

如：ASCII码就是一个定长编码。在我们的ASCII码表中，每一个字符占一个字节，而8个二进制位就表示一个字节，也就是说，我们的ASCII码是固定长度为8的二进制表示的定长编码，如字符’a’的ASCII码表示为：97,其8位二进制表示为：01100001。

定长编码的好处在于：由于定长编码代表一个字符的长度是确定的，因此，我们在编码和解码时都比较方便，直接按照这个长度截取并编码/解码即可。

# 以下二进制位代表的是一个ASCII码字符的二进制串，请转换成实际的字符
01100001010000010011001000110000
# 由于ASCII码是定长编码，每8个二进制位代表一个字符，因此，我们先将上面的二进制以8个为一个单位拆开
01100001 01000001 00110010 00110000
# 然后针对每一段8位2进制找到期对应的ASCII代表的字符
    a        A        2       0
# 因此，上述二进制信息代表的是字符“aA20”
1
2
3
4
5
6
7

变长编码

有效的变长编码：字符编码不能是其他字符编码的前缀（非绝对，只是比较常用）。如果把编码看成是二叉树上的路径，那么所有字符都落在叶子节点上。

# 假设我们将a、A和0三个字符分别编码成以下信息：
# a
01
# A
10
# 0
11

# 我们用一个二叉树来表示0和1的编码
                    root
                /            \
               0               1
           /        \       /      \
          0          1     0         1
                     a     A         0
# 可以看出我们的字符都是落在了二叉树的叶子节点上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

变长编码的应用场景：在网络传输的过程中，通过变长编码提升网络传输的效率（需要传输的数据大小变小了，传输效率自然就高了）

哈夫曼编码

哈夫曼编码是最优的变长编码

统计字符出现频率

哈夫曼编码首先会对我们待编码的字符串进行统计，将每一个字符出现的频率统计出来

建树

统计出每一个字符的出现频率之后，会每次将所有频率中最低的两个字符合并创建成一颗二叉子树，这颗二叉子树的总频率就是两个字符出现频率之和。合并之后再从所有字符频率中（包括新合并子树的频率）再挑出两个最小的创建子树，依次类推，知道将所有字符都放到了一颗二叉树中。

编码

我们将每个路径按照左0右1的原则进行编号，那么，我们每个字符所代表的编码就已经呼之欲出了。

# 假设一篇文章中出现了以下字符
hello

# 首先统计每个字符出现的频率
h: 0.2
e: 0.2
l: 0.4
o: 0.2

# 递归地将每个字母按照出现频率最低的两两建树
# 首先将h和e放到一颗二叉子树中
         0.4
       /     \
      h       e
# 然后再将新建的子树放回概率池，剩余的字符概率最低的进行建树
# 发现新建子树和字符o概率最低
             0.6
          /       \
         o        0.4
               /       \
              h         e
# 最后将l于新建子树合并
                1
            /        \
           l         0.6
                  /        \
                o          0.4
                        /        \
                       h          e
# 接下来我们将每条边都按照左0右1的规则进行编号

                 1
          0 /         \ 1
           l          0.6
                 0 /        \ 1
                 o          0.4
                       0 /        \ 1
                        h          e
# 那么，我们每个字符的编码就出来了
l: 0
o: 10
h: 110
e: 111

# 现在我们来对以下编码进行解码试试
1101110010

# 变长编码的解码规则是尽可能匹配更长的编码，匹配不上再缩小范围，按照这个规则，我们把编码划分为已下几块
110 111 0 0 10
# 依次编码得
h    e  l l  o
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

公式

哈夫曼编码实际上是在求解上述公式，即根据出现概率来求解平均长度最短的码字。这也是为什么说哈夫曼编码是最优变长编码的原因。

代码实现

// 利用小顶堆维护频率池最小的节点，npm i heap
const Heap = require("heap");

class HaNode {
  freq: number = 0;
  ch: string = "";
  left: HaNode = null;
  right: HaNode = null;
  constructor(
    freq: number,
    ch: string,
    left: HaNode = null,
    right: HaNode = null
  ) {
    this.freq = freq;
    this.ch = ch;
    this.left = left;
    this.right = right;
  }
}

export type HaffmanInfo = {
  root: HaNode;
  codes: Record<string, string>;
  codeKey: Record<string, string>;
  freqInfo: Record<string, number>;
};

export type HaffmanEncodeResult = {
    detail: Record<string, string>;
    code: string;
    freqInfo: Record<string, number>;
    haffmanInfo: HaffmanInfo
};

class HaffmanCode {
  // 由于建树时需要每次获取两个出现频次最低的节点，因此利用小顶堆实现
  heap: Heap<HaNode>;
  constructor() {
    this.heap = new Heap((a: HaNode, b: HaNode) => a.freq - b.freq);
  }
  /**
   * 统计每个字符出现的次数
   * @param str
   * @returns
   */
  statistics(str: string): Record<string, number> {
    const map: Record<string, number> = {};
    for (let c of str) {
      if (map[c] === undefined) map[c] = 0;
      map[c]++;
    }
    return map;
  }
  /**
   * 根据构建的二叉字典树构建成哈夫曼编码
   * @param root 二叉树根节点
   * @param prefix 当前节点的前缀字符串
   * @param codes 储存字符和哈夫曼编码的映射关系，用于编码
   * @param codeKey 储存哈夫曼编码与字符的映射关系，用于解码
   * @returns
   */
  __extra_code(
    root: HaNode,
    prefix: string = "",
    codes: Record<string, string>,
    codeKey: Record<string, string>
  ): void {
    if (root.ch !== "") {
      codes[root.ch] = prefix;
      codeKey[prefix] = root.ch;
      return;
    }
    this.__extra_code(root.left, prefix + "0", codes, codeKey);
    this.__extra_code(root.right, prefix + "1", codes, codeKey);
  }
  /**
   * 预处理哈夫曼编码的一些信息，如手机字符出现频次，创建小顶堆，建树，字符编码银蛇
   * @param str 
   * @returns 
   */
  __predo(str: string): HaffmanInfo {
    // 统计每个字符出现的频次
    const map = this.statistics(str);
    // 按照频次将节点插入到小顶堆中
    Object.keys(map).forEach((key) => {
      this.heap.insert(new HaNode(map[key], key));
    });
    // 每次从小顶堆弹出两个元素（频次最少）合并成一个节点
    while (this.heap.size() > 1) {
      const a: HaNode = this.heap.pop();
      const b: HaNode = this.heap.pop();
      this.heap.insert(new HaNode(a.freq + b.freq, "", a, b));
    }
    const root: HaNode = this.heap.top();
    const codes: Record<string, string> = {};
    const codeKey: Record<string, string> = {};
    this.__extra_code(root, "", codes, codeKey);
    return {
      root,
      codes,
      freqInfo: map,
      codeKey
    };
  }
  /**
   * 编码
   * @param str 
   * @returns 
   */
  encode(str: string): HaffmanEncodeResult {
    const info = this.__predo(str);
    const { codes, freqInfo } = info;
    return {
      detail: codes,
      code: str
        .split("")
        .map((char) => codes[char])
        .join(""),
      freqInfo,
      haffmanInfo: info
    };
  }
  /**
   * 解码
   * @param str 
   * @param info 包含编码信息与字符映射信息等编码相关信息，用于解码
   * @returns 
   */
  decode(str: string, info: HaffmanInfo): string {
    let pos = 0;
    let res = '';
    let buff = '';
    const {codeKey} = info;
    while(str[pos]) {
        buff += str[pos++]
        if(codeKey[buff]) {
            res+=codeKey[buff];
            buff = '';
        }
    }
    return res;
  }
}

const haffmanCode = new HaffmanCode();

const { detail, code, freqInfo, haffmanInfo } = haffmanCode.encode(
  "hello, my name is kiner tang! would you like some milk?"
);

Object.keys(detail).forEach((key) => {
  console.log(
    `字符【${key}(出现频次：${freqInfo[key]})】的哈夫曼编码为：${detail[key]}`
  );
});

console.log("完整哈夫曼编码：", code);

console.log(`解码：${haffmanCode.decode(code, haffmanInfo)}`);

// 字符【 (出现频次：10)】的哈夫曼编码为：00
// 字符【l(出现频次：5)】的哈夫曼编码为：010
// 字符【!(出现频次：1)】的哈夫曼编码为：01100
// 字符【s(出现频次：2)】的哈夫曼编码为：01101
// 字符【n(出现频次：3)】的哈夫曼编码为：0111
// 字符【o(出现频次：4)】的哈夫曼编码为：1000
// 字符【t(出现频次：1)】的哈夫曼编码为：100100
// 字符【,(出现频次：1)】的哈夫曼编码为：100101
// 字符【d(出现频次：1)】的哈夫曼编码为：100110
// 字符【?(出现频次：1)】的哈夫曼编码为：100111
// 字符【i(出现频次：4)】的哈夫曼编码为：1010
// 字符【m(出现频次：4)】的哈夫曼编码为：1011
// 字符【a(出现频次：2)】的哈夫曼编码为：11000
// 字符【g(出现频次：1)】的哈夫曼编码为：110010
// 字符【w(出现频次：1)】的哈夫曼编码为：110011
// 字符【h(出现频次：1)】的哈夫曼编码为：110100
// 字符【r(出现频次：1)】的哈夫曼编码为：110101
// 字符【u(出现频次：2)】的哈夫曼编码为：11011
// 字符【y(出现频次：2)】的哈夫曼编码为：11100
// 字符【k(出现频次：3)】的哈夫曼编码为：11101
// 字符【e(出现频次：5)】的哈夫曼编码为：1111
// 完整哈夫曼编码： 1101001111010010100010010100101111100000111110001011111100101001101001110110100111111111010100100100110000111110010011000011001110001101101010011000111001000110110001010101110111110001101100010111111001011101001011101100111
// 解码：hello, my name is kiner tang! would you like some milk?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185