发信人: fishy()
整理人: winsy(2003-03-05 16:32:51), 站内信件
|
霍夫曼树(HuffmAn Tree，以下简称ht)压缩法：
（据我猜测，RAR使用的就是这种算法）
数据结构：
二叉树（如果不懂什么是二叉树，找一本大学的《数据结构》课本
看看，否则下面的很多名词都会看不懂）
由于VB现在还不支持链表，所以记录二叉树有一点麻烦。建议使用
以下的数据结构：
Public Type Node
DAtA As DAtAType '记录数据
Left As Integer '左子树的下标
Right As Integer '右子树的下标
End Type
Public HuffmAnTree() As Node
如果有必要，还可以在Node中定义一个FAther As Integer来记录
父节点。
算法原理：
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串去替换原来的字符并按照二进制处理，
就可以得到压缩后的文件了。
--
Dim fishy As Friend
回复时请打勾
------------
欢迎大家访问酷码工作室：http://comma.my163.net
※ 来源:．月光软件站 http://www.moon-soft.com．[FROM: 202.103.40.2]
|
|