Huffman树简单实现
?最近在学习数据结构，但一直没做笔记，只知道敲代码。现在开始记录自己所敲类容。
?一、准备知识
?????? 1、优先队列：是带有优先权的元素序列。普通队列实现是采用先进先出的方式，优先队列是优先权最小的元素先出队列。优优先队列的长度是所包含元素的个数。空优先队列长度为0；
?????? 2、完全二叉树：有严格的形状要求，从根结点到每一层的结点从左到右连续填充，除了最后一层外，其余各层都是满的，并且最下一层的结点都集中在该层的最左边。
?????? 3、最小堆：如果一棵二叉树每一个结点存储的值都小于或等于其子节点的值，则称该二叉树具有堆序性质。堆是具有堆序性质的完全二叉树。
二、堆的操作（数组实现）
????? 1、堆的插入：1）扩展堆到下一个空闲位置，作为一个待填充的槽；
??????????????????????????2）比较槽所对应的父结点与新插入元素的大小，如果小于或等于新插入的元素，则将新结点复制到槽结点。否则将槽所对应的父结点值复制到槽结点处，同时将槽上移到父节点处。
??????????????????????????3）反复执行2）将父节点下移动，槽结点上移操作。直到父节点值小于或等于要插入的元素的值，或者槽到达根结点，这时将插入元素值复制到槽结点。
????? 2、堆的删除：1）复制堆最后一个元素到变量last中，同时将最后一个元素置为null；
??????????????????????????2）删除根结点（优先权最小结点），同时将根结点处作为一个槽；
????????????????????????? 3）获取槽结点子节点中最小元素值与last元素值做比较，如果大于last结点值，则将last结点值复制到槽结点，同时结束。否则将子节点中最小值复制到槽结点，同时将槽结点下移动到最小子结点位置。
??????????????????????????4）反复执行3）将槽结点下移动，直到last大于任何一个子节点或者槽结点到达一个叶结点位置，这时将last值复制到槽结点并结束。
????? 3、堆排序：每次从堆中获取最小权值，获取的序列就是一个有序序列。
三、Huffman编码：一种变长的编码。Huffman编码为字符分配代码，其长度取决于对应字母使用的频率或权。每个字符的Huffman编码是从Huffman树（一种满二叉树）中获得。Huffman树中的每个叶结点对应一个字符，叶结点对应的权重就为该字符使用的频率，其目的按照最小外部路径权重建立一棵二叉树。一个叶结点的加权路径长度定义为权乘以深度。具有最小外部路径权重的二叉树就是（对于给定的叶节点集合）具有加权路径长度之和最小的二叉树。权大的叶结点深度小，因而它相对于总路径长度的花费最小。因此其他叶结点的权值小，则在树的较深处。
????? 1、建立n个结点的Huffman树过程
?????????? 1）创建n个初始的Huffman树，每棵树只包含一个结点，叶结点的记录对应字符及其频率。将n棵树按照权的大小进行排序，接着获取两颗权最小的树，把他们作为两颗子树链接到一个分支结点下面，且分支结点的权为该两个结点的权值和，再把所得到的新树放回到序列中适当位置，使得权顺序保持为升序。重复上述步骤，知道序列中只剩下一个元素，则Huffman树建立完毕。
四、代码实现
????? 1、优先队列ADT
?package com.structure.huffman;
/**
?* 优先队列ADT
?* @author hudp
?* 2011-11-28
?*/
public interface PriorityQueue {
??? //添加新节点
?void insert(Comparable val);
?//移除节点
?Comparable remove();
?//返回节点数
?int size();
?//获取优先级最小的节点
?Comparable get();
?//清除数据
?void clear();
}
2、堆实现优先队列
package com.structure.huffman;
/**
?* 采用最小堆实现优先队列
?* @author hudp
?* 2011-11-28
?*/
public class HeapPriorityQueue implements PriorityQueue {
?private final int DEFAULT_SIZE = 10;//默认大小10
?private Comparable[] array;
?private int count ;
?
? public HeapPriorityQueue(){
?? array = new Comparable[DEFAULT_SIZE];
?? count = 0;
? }
?@Override
?public void insert(Comparable val) {
??if(array.length >= count){
???expand();
??}
??int holePoint = count ++;
??while(holePoint > 0){
???int parentPoint = (holePoint -1)/2;
???if(array[parentPoint].compareTo(val) < 0){
????break;
???}
???array[holePoint] = array[parentPoint];
???holePoint = parentPoint;
??}
??array[holePoint] = val;
?}
?//扩展数组长度为先前的2倍
?private void expand() {
??Comparable[] newArr = new Comparable[array.length * 2];
??for(int i = 0 ; i < array.length ; i ++){
???newArr[i] = array[i];
??}
??array = newArr;
?}
?@Override
?public Comparable remove() {
??if(count <= 0){
???throw new IllegalStateException("error count !");
??}
??Comparable min = array[0];
??Comparable last = array[--count];
??array[count] = null;
??int holePoint = 0;
??int child = holePoint * 2 + 1;//left节点
??while(child < count){
???if(child + 1 < count && array[child].compareTo(array[child+1]) > 0){
????child ++;
???}
???if(array[child].compareTo(last) > 0){
????break;
???}
???array[holePoint] = array[child];
???holePoint = child;
???child = holePoint * 2 + 1;
??}
?? array[holePoint] = last;
?? return min;
?}
?@Override
?public int size() {
??return count;
?}
?@Override
?public Comparable get() {
??if(count <= 0 ){
???throw new IllegalStateException("no data !");?
??}
??return array[0];
?}
?@Override
?public void clear() {
??for(int i = 0 ; i < count ; i ++){
???array[i] = null;
??}
??count = 0;
?}
}
3、Huffman树实现
package com.structure.huffman;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
?* Huffman tree实现
?* @author hudp
?* 2011-11-28
?*/
public class HuffmanTree {
?private CodeMember[] codeTable;
?private final int SYS_LEN = 256;//可以接受256个8位字符
?private HuffNode root;//Huffman树根
?public HuffmanTree() {
??codeTable = new CodeMember[SYS_LEN];
??root = null;
?}
?//Huffman树节点
?private class HuffNode implements Comparable {
??char letter ;//ASCII字符
??int frequency;//出现频率
??HuffNode left, right;
??public HuffNode() {
???letter = '\0';
???frequency = 0;
???left = right = null;
??}
??@Override
??public int compareTo(Object other) {
???HuffNode otherNode = (HuffNode) other;
???return this.frequency = otherNode.frequency;
??}
?}
?//编码表
?private class CodeMember {
??String code;
??int frequency;
??public CodeMember() {
???frequency = 0;
???code = "";
??}
?}
?//创建树
?public void buildHuffTree(String text) {
??for (int i = 0; i < text.length(); i++) {
???int k = text.charAt(i);
???if (null == codeTable[k]) {
????codeTable[k] = new CodeMember();
???}
???codeTable[k].frequency++;
??}
??PriorityQueue pq = new HeapPriorityQueue();
??root = buildHuffTree(pq);
??createCode();
?}
?//创建树
?private HuffNode buildHuffTree(PriorityQueue pq) {
??for (int i = 0; i < codeTable.length; i++) {
???if (null != codeTable[i]) {
????HuffNode node = new HuffNode();
????node.letter = (char) i;
????node.frequency = codeTable[i].frequency;
????pq.insert(node);
???}
??}
??while (pq.size() > 1) {
???HuffNode childLeft = (HuffNode) pq.remove();
???HuffNode childRight = (HuffNode) pq.remove();
???HuffNode parent = new HuffNode();
???parent.frequency = childLeft.frequency + childRight.frequency;
???parent.left = childLeft;
???parent.right = childRight;
???pq.insert(parent);
??}
??return (HuffNode) pq.remove();
?}
?//创建编码
?private void createCode() {
??String code = "";
??createCode(root, code);
?}
?private void createCode(HuffNode ref, String code) {
??if (ref == null) {
???return;
??} else if (null == ref.left && null == ref.right) {
???int i = ref.letter;
???codeTable[i].code = code;
??} else {
???createCode(ref.left, code + "0");
???createCode(ref.right, code + "1");
??}
?}
?//编码
?public String encode(String text) {
??StringBuilder sbf = new StringBuilder();
??int len = text.length();
??for (int i = 0; i < len; i++) {
???int k = text.charAt(i);
???if (null == codeTable[k]) {
????return null;
???}
???sbf.append(codeTable[k].code);
??}
??return sbf.toString();
?}
?//解码
?public String decode(String code) {
??StringBuilder sbf = new StringBuilder();
??int k = 0;
??while (k < code.length()) {
???HuffNode ref = root;
???while (null != ref.left && null != ref.right) {
????int l = code.charAt(k);
????if ('0' == l) {
?????ref = ref.left;
????} else if ('1' == l) {
?????ref = ref.right;
????} else {
?????throw new IllegalArgumentException("error input!");
????}
????k++;
???}
???sbf.append(ref.letter);
??}
??return sbf.toString();
?}
?public static void main(String[] args) throws IOException {
??System.err.println("input data :");
??BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
??HuffmanTree ht = new HuffmanTree();
??String text = br.readLine();
??ht.buildHuffTree(text);
??String encode = ht.encode(text);
??System.err.println("edcode:" + encode);
??System.err.println("decode:" + ht.decode(encode));
?}
}
说明：
?????? 1、编码：字符用编码标记：从根结点开始，分别把'0'（对应左子节点那条边）或'1'（对应右子结点的那条边），其编码就是从根结点到对应字符叶结点路径的二进制编码。在遍历的过程中，每当遇到一个叶结点，就把该结点包含的字符所对应的编码串填入编码表中。
???????2、反编码：从左到右逐位扫描编码串，直到确定一个字符位置。（从根结点开始进行反编码，根据每一位的值'0‘或'1‘选择左分支还是右分支，直到到达一个叶结点，取得其对应的字符）
?????? 3、前缀特性：如果一组编码中任何一个编码都不是另外一个编码的前缀，则称这组代码符合前缀特性。这种前缀特性保证了代码串被反编码时不会有多种可能。由于任何一个编码的前缀都对应一个分支结点，而每个编码都对应一个字符，所以Huffman编码符合前缀特性。
