Go语言视频零基础入门到精通

javalearner

如何进行哈夫曼编码：
        




哈夫曼树的建立过程（FLASH动画）

   
   
      
  
             这里随便写了个用java实现的哈夫曼编码的算法（二叉树表示）。   
        /**
         * @(#) 岑村高科
         */
        package cn.javayy.struct;
         
        /**
         * 定义了一种接口，要进行编码的最小单元类必需实现些接口
         * @author boss
         *
         * create on : 下午10:56:59 2009-5-19
         */
        public interface Combinable<T> extends Comparable<T> {
         
            T combinate(T a,T b);
            
        }
        =====================================================
        /**
         * @(#) 岑村高科
         */
        package cn.javayy.struct;
         
        /**
         * the huffman tree Class
         * <p> 哈夫曼树，包括当前节点数据信息，左节点，右节点信息。
         * @author boss
         *
         * create on : 下午10:16:23 2009-5-19
         */
        public class HuffmanTree<T extends Combinable<T>> implements Comparable<HuffmanTree<T>>{
         
            /**the root of huffman tree*/
            private T root;
            /**the left node of huffman tree*/
            private HuffmanTree<T> left;
            /**the right node of huffman tree*/
            private HuffmanTree<T> right;
            /**哈夫曼编码字符串，如:0000110*/
            private String huffmanCodeString = "";
            /**是否对最终生成的哈夫曼进行过编码操作*/
            private static boolean isSettedHuffmanCoderString = false;
            
            public T getRoot() {
               return root;
            }
         
         
            public void setRoot(T root) {
               this.root = root;
            }
         
         
            public HuffmanTree<T> getLeft() {
               return left;
            }
         
         
            public void setLeft(HuffmanTree<T> left) {
               this.left = left;
            }
         
         
            public HuffmanTree<T> getRight() {
               return right;
            }
         
         
            public void setRight(HuffmanTree<T> right) {
               this.right = right;
            }
         
         
            /**
             * 重写此方法用于递归合并节点后进行排序操作
             */
            @Override
            public int compareTo(HuffmanTree<T> o) {
               // TODO Auto-generated method stub
               return o.getRoot().compareTo(this.getRoot());
            }
            
            @Override
            public String toString(){
               return "the root:" + this.getRoot()
                      + "
the left:" + this.getLeft()
                      + "
the right:" + this.getRight();
            }
            
            /**
             * 对最终生成的树进行哈夫曼编码，使每个叶子节点生成01的路径编码
             */
            private void setHuffmanCoderString(){
               HuffmanTree<T> left = this.getLeft();
               //如果有左节点则在路径中追加"0"
               if(left != null){
                   left.huffmanCodeString = this.huffmanCodeString + "0";
                   left.setHuffmanCoderString();//递归编码
               }
               HuffmanTree<T> right = this.getRight();
               //如果有右节点则在路径中追加"1"
               if(right != null){
                   right.huffmanCodeString = this.huffmanCodeString + "1";
                   right.setHuffmanCoderString();//递归编码
               }
            }
            
            public void printHuffmanCoderString(){
               //打印最终生成树的哈夫曼编码前要进行编码操作，
               //且此操作只执行一次，所以用全局标识变量判断
               if(!HuffmanTree.isSettedHuffmanCoderString){
                   this.setHuffmanCoderString();
                   HuffmanTree.isSettedHuffmanCoderString = true;//标识已执行过编码
               }
        //如果是叶子节点（即要编码的单元），则打印出编码信息，如果是非叶子结点（中间临时生成的节点），则不打印
             if(this.left == null && this.right == null)
               System.out.println("the " + this.getRoot() + " huffmanCoder:" +
         this.huffmanCodeString);
               if(this.left != null)
                   this.left.printHuffmanCoderString();//递归打印
               if(this.right != null)
                   this.right.printHuffmanCoderString();//递归打印
            }
        }
        ==================================================
        /**
         * @(#) 岑村高科
         */
        package cn.javayy.struct;
         
        import java.util.Collections;
        import java.util.LinkedList;
        import java.util.List;
         
        /**
         * 用类用于生成一个哈夫曼树
         * @author boss
         *
         * create on : 下午10:51:39 2009-5-19
         */
        public class HuffmanTreeFactory<T extends Combinable<T>> {
         
            /**初始时一个list列表当作要编码的单元类的容器*/
            private List<HuffmanTree<T>> HuffmanTreeCollection;
            
        //  public HuffmanTreeFactory(){}
            /**
             * @param unitClasses 待编码的单元类集合
             */
            public HuffmanTreeFactory(List<T> unitClasses){
               if(unitClasses == null || unitClasses.size() == 0)
                   throw new IllegalArgumentException(
               "the unit classes collection can"t be empty");
               HuffmanTreeCollection = new LinkedList<HuffmanTree<T>>();
               //初始化哈夫曼集合容器
               for(T unitClass : unitClasses){
                   HuffmanTree<T> huffmanTree = new HuffmanTree<T>();
                   huffmanTree.setRoot(unitClass);
                   huffmanTree.setLeft(null);
                   huffmanTree.setLeft(null);
                   HuffmanTreeCollection.add(huffmanTree);
               }
               Collections.sort(HuffmanTreeCollection);
            }
            /**
             * 将待编码的哈夫曼集合处理成只含有一个元素的集合，则这最后一个元素
             * 即为最终生成的哈夫曼树
             */
            private void generateHuffmanTree(){
               while(true){
                   if(HuffmanTreeCollection == null || HuffmanTreeCollection.size() <= 1)
                      break ;
                   //处理之前一定要重新排序，这是哈夫曼编码的关键原理
                   Collections.sort(HuffmanTreeCollection);
                   HuffmanTree<T> huffmanTreeOne = HuffmanTreeCollection.remove(0);
                   HuffmanTree<T> huffmanTreeTwo = HuffmanTreeCollection.remove(0);
                   HuffmanTree<T> huffmanTreeNew = new HuffmanTree<T>();
                   //将集合中前面两个元素合并成一个元素插到集合中去
                   //并将第一个元素和第二个元素分别作为新元素的左，右节点
                   huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().
             combinate(huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));
                   huffmanTreeNew.setLeft(huffmanTreeOne);
                   huffmanTreeNew.setRight(huffmanTreeTwo);
                   HuffmanTreeCollection.add(huffmanTreeNew);
               }
            }
            
            /**
             *  
             * @return 生成最终的哈夫曼树
             */
            public HuffmanTree<T> getHuffmanTree(){
               generateHuffmanTree();
               return this.HuffmanTreeCollection.get(0);
            }
        }
        ================================================
        /**
         * @(#) 岑村高科
         */
        package cn.javayy.struct;
         
        import java.io.Serializable;
         
        /**
         * 自定义一个用于测试的单元类
         * @author boss
         *
         * create on : 下午09:53:07 2009-5-19
         */
        public class UnitClass implements Serializable,Combinable<UnitClass>{
         
            /**
             * serialVersionUID
             */
            private static final long serialVersionUID = -4109190579335512743L;
            
            /**出现概率数据*/
            private int rate;
            
            public UnitClass(int rate){
               this.rate = rate;
            }
            
            public int getRate() {
               return rate;
            }
         
         
         
            public void setRate(int rate) {
               this.rate = rate;
            }
         
         
         
            /**
             * implements thid compartTo() in order to sort the
      * collection stored from unitclass
             */
            @Override
            public int compareTo(UnitClass o) {
               return o.getRate() > this.rate ? 1: o.getRate() < this.rate ? -1 : 0;
            }
            
            @Override
            public String toString(){
               return "the rate is:" + rate;
            }
         
            /**
             * 重写此方法用于哈夫曼编码时可以合并两个分支点信息
             */
            @Override
            public UnitClass combinate(UnitClass a, UnitClass b) {
               if(a == null || b == null)
                   return null;
               return new UnitClass(a.getRate() + b.getRate());
            }
        }
        ========================================
        /**
         * @(#) 岑村高科
         */
        package cn.javayy.struct;
         
        import java.util.ArrayList;
        import java.util.List;
         
        /**
         * @author boss
         *
         * create on : 下午10:03:12 2009-5-19
         */
        public class Main {
         
            
            public static void main(String[] args){
               List<UnitClass> l = new ArrayList<UnitClass>();
               l.add(new UnitClass(2));
               l.add(new UnitClass(4));
               l.add(new UnitClass(10));
               l.add(new UnitClass(7));
               l.add(new UnitClass(20));
               HuffmanTreeFactory<UnitClass> factory = new HuffmanTreeFactory<UnitClass>(l);
        //     System.out.println(factory.getHuffmanTree());
               factory.getHuffmanTree().printHuffmanCoderString();
            }
        }
        =========================================
        打印结果：
        the the rate is:20 huffmanCoder:0
the the rate is:10 huffmanCoder:10
the the rate is:2 huffmanCoder:1100
the the rate is:4 huffmanCoder:1101
the the rate is:7 huffmanCoder:111
        
  
        
      
      
        
      
      
      
     
   

   
     
     
      
      

        
      

        
      
     
   

  


源码下载：http://file.javaxxz.com/2014/11/9/000437937.zip