《算法设计与分析》--哈夫曼编码随笔

1、概述：哈弗曼编码是广泛应用于数据文件压缩的十分有效的编码方法，该算法使用的是字符在文件中出现的频率来建立一个用0,1表示各个字符的最优表示方式。

 

 

2、前缀码：对于每一个字符都要去规定一个0,1串代表其代码，并且要求每一个字符的代码都不是其他字符代码的前缀。

所以对于上面的表中的给定的0,1串001011101我们可以唯一的分解成为0,0,101,1101,所以它的编码码为aabe。

3、表示前缀码：我们可以使用二叉树作为前缀码的数据结构，把树叶看作是给定的字符。并且把从树根到该字符的路径看做每个字符的前缀码。其实表示最有前缀码的二叉树总是一颗完全二叉树，也即树中的任意一个节点都有两个儿子节点。

哈夫曼编码的方式是以字底向上的方式构造表示最优前缀码的二叉树T，下面给出哈夫曼算法的代码段：

public static class Huffman implements Comparable{

Bintree tree;
float weight;//权值

private Huffman(Bintree tt,float ww){
tree = tt;
weight = ww;
}

public int compareTo(Object x){

float xw = ((Huffman)x).weight;
if(weight<xw)return -1;
if(weight==xw)return 0;
return 1;
}
}