怎样将建立好的哈夫曼树保存在文件中

怎样将建立好的哈夫曼树保存在文件中

哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码.
　　首先介绍什么是哈夫曼树.哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树.所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层,叶结点到根结点的路径长度为叶结点的层数）.树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n).可以证明哈夫曼树的WPL是最小的.
　　哈夫曼在上世纪五十年代初就提出这种编码时,根据字符出现的概率来构造平均长度最短的编码.它是一种变长的编码.在编码中,若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列,则编码的平均长度是最小的.（注：码字即为符号经哈夫曼编码后得到的编码,其长度是因符号出现的概率而不同,所以说哈夫曼编码是变长的编码.）
　　一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空.（为方便在计算机上实现算法,一般还要求以Ti的权值Wi的升序排列.）
　　二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和.
　　三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中.
　　四、重复二和三两步,直到集合F中只有一棵二叉树为止.
　　用C语言实现上述算法,可用静态的二叉树或动态的二叉树.若用动态的二叉树可用以下数据结构： struct tree{
　　float weight; /*权值*/　　union{　　char leaf; /*叶结点信息字符*/
　　struct tree *left; /*树的左结点*/　　};　　struct tree *right; /*树的右结点*/　　};　　struct forest{ /*F集合,以链表形式表示*/
　　struct tree *ti; /* F中的树*/
　　struct forest *next; /* 下一个结点*/　　};　　例：若字母A,B,Z,C出现的概率为：0.75,0.54,0.28,0.43；则相应的权值为：75,54,28,43.
　　构造好哈夫曼树后,就可根据哈夫曼树进行编码.例如：上面的字符根据其出现的概率作为权值构造一棵哈夫曼树后,经哈夫曼编码得到的对应的码值.只要使用同一棵哈夫曼树,就可把编码还原成原来那组字符.显然哈夫曼编码是前缀编码,即任一个字符的编码都不是另一个字符的编码的前缀,否则,编码就不能进行翻译.例如：a,b,c,d的编码为：0,10,101,11,对于编码串：1010就可翻译为bb 或ca,因为b的编码是c的编码的前缀.刚才进行哈夫曼编码的规则是从根结点到叶结点（包含原信息）的路径,向左孩子前进编码为0,向右孩子前进编码为 1,当然你也可以反过来规定.
　　这种编码方法是静态的哈夫曼编码,它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并必须把树的信息保存起来,即把字符 0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来,（用4Bytes的长度存储频率值,频率值的表示范围为 0--2^32-1,这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码,并把编码后得到的码字存储起来.静态哈夫曼编码方法有一些缺点：一、对于过短的文件进行编码的意义不大,因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；二、进行哈夫曼编码,存储编码信息时,若用与通讯网络,就会引起较大的延时；三、对较大的文件进行编码时,频繁的磁盘读写访问会降低数据编码的速度.
　　因此,后来有人提出了一种动态的哈夫曼编码方法.动态哈夫曼编码使用一棵动态变化的哈夫曼树,对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的,编码和解码使用相同的初始哈夫曼树,每处理完一个字符,编码和解码使用相同的方法修改哈夫曼树,所以没有必要为解码而保存哈夫曼树的信息.编码和解码一个字符所需的时间与该字符的编码长度成正比,所以动态哈夫曼编码可实时进行.动态哈夫曼编码比静态哈夫曼编码复杂的多,有兴趣的读者可参考有关数据结构与算法的书籍.
　　前面提到的JPEG中用到了哈夫曼编码,并不是说JPEG就只用哈夫曼编码就可以了,而是一幅图片经过多个步骤后得到它的一列数值,对这些数值进行哈夫曼编码,以便存储或传输.哈夫曼编码方法比较易懂,大家可以根据它的编码方法,自己编写哈夫曼编码和解码的程序.