算法原理:
ht首先被提出来,是为了解决这样的问题:
对于N种数据(比如5种数据:A、B、C、D、E),在出现的频率已知的情况下(比如分别出现了3、5、2、6、4次),如何用不等长的01串来分别表示它们,使01串的总长度最短。
比如原始串:ABADBCBDABEDBDEDCEDE
对于这个问题,首先得到:任何一个01串都不能是其他01串的前缀。也就是说,如果用“10”来表示A,那么其他01串就不能以“10”开头。
建立01串的步骤如下:
首先找到出现最少的两个数据(A、C),分别以它们为左右子树,建立一个二叉树。并将它们出现次数之和作为根节点:
1)
5 5B 6D 4E
/ \
3A 2C
然后从剩下的4个数举重找到两个最小的,做同上的操作,知道只剩一个数据为止:
2)
5 9 6D
/ \ / \
3A 2C 5B 4E
3)
11 9
/ \ / \
5 6D 5B 4E
/ \
3A 2C
4)
20
/ \
11 9
/ \ / \
5 6D 5B 4E
/ \
3A 2C
最后从根节点开始,每个左子树填0,右子树填1:
ROOT
/ \
0 1
/ \ / \
0 1D 0B 1E
/ \
0A 1C
这样每个数据对应的01串就是从根节点到数据所在的叶子节点的路 径:
A: 000
B: 10
C: 001
D: 01
E: 11
这样原始串ABADBCBDABEDBDEDCEDE就成了:
000100000110001100100010110110011101001110111
压缩:
把256个Ascii码看作256种数据,分析它们出现的次数,建立ht,得到256个01串。用这256个01串去替换原来的字符并按照二进制处理,就可以得到压缩后的文件了。