Huffman编码处理的是字符以及字符对应的二进制的编码配对问题，分为编码和解码，目的是压缩字符对应的二进制数据长度。我们知道字符存贮和传输的时候都是二进制的(计算机只认识0/1)，那么就有字符与二进制之间的mapping关系。字符属于字符集(Charset), 字符需要通过编码(encode)为二进制进行存贮和传输，显示的时候需要解码(decode)回字符，字符集与编码方法是一对多关系(Unicode可以用UTF-8,UTF-16等编码)。理解了字符集，编码以及解码，满天飞的乱码问题也就游刃而解了。以英文字母小写a为例, ASCII编码中，十进制为97，二进制为01100001。ASCII的每一个字符都用8个Bit(1Byte)编码，假如有1000个字符要传输，那么就要传输8000个Bit。问题来了，英文中字母e的使用频率为12.702%，而z为0.074%，前者是后者的100多倍，但是确使用相同位数的二进制。可以做得更好，方法就是可变长度编码，指导原则就是频率高的用较短的位数编码，频率低的用较长位数编码。Huffman编码算法就是处理这样的问题。
Huffman编码
Java实现
Huffman编码算法主要用到的数据结构是完全二叉树(full binary tree)和优先级队列。后者用的是java.util.PriorityQueue，前者自己实现(都为内部类)，代码如下:
[java]
static class Tree {
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
}
static class Node implements Comparable {
private String chars = "";
private int frequence = 0;
private Node parent;
private Node leftNode;
private Node rightNode;
@Override
public int compareTo(Node n) {
return frequence - n.frequence;
}
public boolean isLeaf() {
return chars.length() == 1;
}
public boolean isRoot() {
return parent == null;
}
public boolean isLeftChild() {
return parent != null && this == parent.leftNode;
}
public int getFrequence() {
return frequence;
}
public void setFrequence(int frequence) {
this.frequence = frequence;
}
public String getChars() {
return chars;
}
public void setChars(String chars) {
this.chars = chars;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
统计数据
既然要按频率来安排编码表，那么首先当然得获得频率的统计信息。我实现了一个方法处理这样的问题。如果已经有统计信息，那么转为Map即可。如果你得到的信息是百分比，乘以100或1000，或10000。总是可以转为整数。比如12.702%乘以1000为12702，Huffman编码只关心大小问题。统计方法实现如下：
[java]
public static Map statistics(char[] charArray) {
Map map = new HashMap();
for (char c : charArray) {
Character character = new Character(c);
if (map.containsKey(character)) {
map.put(character, map.get(character) + 1);
} else {
map.put(character, 1);
}
}
return map;
}
构建树
构建树是Huffman编码算法的核心步骤。思想是把所有的字符挂到一颗完全二叉树的叶子节点，任何一个非页子节点的左节点出现频率不大于右节点。算法为把统计信息转为Node存放到一个优先级队列里面，每一次从队列里面弹出两个最小频率的节点，构建一个新的父Node(非叶子节点), 字符内容刚弹出来的两个节点字符内容之和，频率也是它们的和，最开始的弹出来的作为左子节点，后面一个作为右子节点，并且把刚构建的父节点放到队列里面。重复以上的动作N-1次，N为不同字符的个数(每一次队列里面个数减1)。结束以上步骤，队列里面剩一个节点，弹出作为树的根节点。代码如下:
[java]
private static Tr