通常数据压缩我们可以使用哈夫曼编码。 下面简单举栗子介绍哈夫曼编码的过程:
哈夫曼编码过程:
假设有词语:A、B、C、D、E、F
- 统计出每个词语出现的次数:A27 B8 C15 D15 E30 F5
- 对词频统计结果排序:F5、B8、C15、D15、A27、E30 // 从小到大
13
/ \
5/ \8
/ \
F B F5 < B8,在左节点。
产生的新节点数据排序后变成:13、C15、D15、A27、E30
28
/ \15
/ \
13 C
/ \
5/ \8
/ \
F B 13 < C15,在左节点。
产生的新节点数据排序后变成:28、D15、A27、E30 ---> D15、A27、28、E30
28 42
/ \15 15/ \27
/ \ / \
13 C D A
/ \
5/ \8
/ \
F B D15 < A27,在左节点。
产生的新节点数据排序后变成:42、28、E30 ---> 28、E30、42
58
/ \30
/ \
28 E 42
/ \15 15/ \27
/ \ / \
13 C D A
/ \
5/ \8
/ \
F B 28 < E30,在左节点。
产生的新节点数据排序后变成:42、58
100
/ \
/ \
42 58
15/ \27 / \30
/ \ / \
D A 28 E
/ \15
/ \
13 C
/ \
5/ \8
/ \
F B
一棵哈夫曼树就构建完成。
- 对树进行编码:左子树为0,右子树为1。
100
0/ \1
/ \
42 58
0/ \1 0/ \1
/ \ / \
D A 28 E
0/ \1
/ \
13 C
/ \
0/ \1
/ \
F B
编码结果:
A: 01
B: 1001
C: 101
D: 00
E: 11
F: 1000
这里有原来的数据字节长度编码成了简单的位数。不重复且大量压缩的数据量。