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编码符合前缀特性。