哈夫曼编码主要用于数据压缩,用更少的位表示更多的数据。
首先对原始数据进行统计,计算每个字符出现的次数,然后建立哈夫曼树。
哈夫曼树也叫最优二叉树(哈夫曼树)。
解码时,对编码后的数据,从哈夫曼树的根出发,遇到一个叶子节点,则译出一个字符,重复此步骤,直到译出所有字符。
建立哈夫曼树的标准是,总长最短,译码时,结果唯一。每个字符的编码不能是其它字符的前置。
public class Node<T> {
int key;
T charData;
Node leftChild;
Node rightChild;
public void displayNode(){
}
}
public class Tree implements Comparable<Tree>{
private Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
/**
*中序遍历法
*/
public void inDisplay(Node node){
if (node!=null){
inDisplay(node.leftChild);
System.out.println(node.key+":"+node.charData);
inDisplay(node.rightChild);
}
}
public void postDisplay(Node node){
if (node!=null){
postDisplay(node.leftChild);
postDisplay(node.rightChild);
System.out.print(node.key+":"+node.charData);
}
}
@Override
public int compareTo(Tree o) {
if (this.root.key>o.root.key){
return 1;
}else if (this.root.key==o.root.key){
return 0;
}else {
return -1;
}
}
}
public class Huffman {
private Map<Character,Integer> map=new HashMap<>();
private Map<Character,String> ce=new HashMap<>();
private PriorityQueue<Tree> trees=new PriorityQueue<>();
private String source;
private String result;
public void init(String source){
this.source=source;
char[] chars= source.toCharArray();
for (char c :chars){
if (!map.containsKey(c)){
map.put(c,1);
}else {
map.put(c,map.get(c)+1);
}
}
afterInit();
}
private void afterInit() {
map.forEach((c,count)->{
Node<Character> node=new Node<>();
node.key=count;
node.charData=c;
Tree tree=new Tree();
tree.setRoot(node);
trees.add(tree);
});
}
public void build(){
while (this.trees.size()>1){
Tree left=this.trees.poll();
Tree right=this.trees.poll();
Node node=new Node();
node.key=left.getRoot().key+right.getRoot().key;
node.leftChild=left.getRoot();
node.rightChild=right.getRoot();
left.setRoot(node);
this.trees.add(left);
}
}
public void encoding(){
Tree tree=this.trees.peek();
this.encoding(tree.getRoot(),"");
}
public String encodingResult(){
StringBuilder sb=new StringBuilder();
char[] chars= source.toCharArray();
for (char c :chars){
sb.append(ce.get(c)+' ');
}
return sb.toString();
}
private void encoding(Node<Character> node,String encoding){
if (node!=null){
if (node.leftChild==null && node.rightChild==null){
ce.put(node.charData,encoding);
}
encoding(node.leftChild,encoding+"0");
encoding(node.rightChild,encoding+"1");
}
}
public void displayTree(){
Tree tree=this.trees.peek();
tree.inDisplay(tree.getRoot());
}
public void displayEncodeing(){
ce.forEach((k,v)->{
System.out.println(k+":"+v);
});
}
public static void main(String[] args) {
String source="ABAACDC";
Huffman huffman=new Huffman();
huffman.init(source);
huffman.build();
huffman.displayTree();
System.out.println("-------");
huffman.encoding();
huffman.displayEncodeing();
System.out.println(source+":"+huffman.encodingResult());
}
}
运行结果:
3:A
7:null
2:C
4:null
1:B
2:null
1:D
-------
A:0
B:110
C:10
D:111
ABAACDC:0 110 0 0 10 111 10 //加空格是为了方便看
原始数据ABAACDC的编码结果是0110001011110
解码时,每取一位,则遍历一次树,发现节点是叶子节点时,则译出一个字符。不是叶子节点,则记住该节点,取下一位后,从上次记录的节点接着遍历。