期权记-ETF期权开户导航 期权记是专业的50ETF300ETF期权开户投资交易导航

浅谈哈夫曼树和哈夫曼编码

  在学习二叉树时看到关于哈夫曼编码的一些描述,兴趣来潮,自己写一个算法。哈夫曼算法使用二叉树

以令人惊讶的方式来压缩数据,以提高数据传输的效率和时间。只有知道哈夫曼编码而不会写代码的童鞋们

才会在网上搜代码,故在这里对哈夫曼编码不做过多介绍。

  实现哈弗曼(Huffman)算法的编码(Encode)与解码(Encode).

  分为以下四步来完成这项编码

  1、Create a Huffman tree for this message.

    2、Create a code table.

    3、Encode the message into binary.

    4、Decode the message from binary back to

      text.

  以下这段代码逻辑正确,测试结果也正确,但仍有一些缺陷还没解决。比如编码时出现频率最多的字符编码位数要最少,

这样得到的编码位数少效率高,这段代码并没做到。其次还有对优先级队列运用不是很准确,不能精准的控制它.remove出的

元素有时不符合我的预期。若有有心人的话,可在这个基础上二次开发,并将更完善的代码发我一份,共同学习。

  本程序是用Java编写的。 

  一、Node.java

package main;    class Node   {      char cData;      int iNumber;      Node leftChild;      Node rightChild;            public void displayNode()      {          System.out.print("Node:");          System.out.print("{");          System.out.print(cData);          System.out.print(",");          System.out.print(iNumber);          System.out.print("}");      }  }

二、HuffmanTree.java

package main;    class HuffmanTree   {      private Node root;            public HuffmanTree(Node root)      {          this.root = root;      }            //获取root的引用,以便用来组装新树      public Node getRoot()      {          return this.root;      }            //获取iNumber的值,代表频率数      public int getNumber()      {          if(root != null)              return root.iNumber;          else              return 0;      }  }

三、Main.java

/******************************************************  Copyright:bupt  Author:zhai bao hua  Begin:2013-10-12  End:2013-10-17  E-mail:carman_loneliness@163.com  Description:实现哈弗曼(Huffman)算法的编码(Encode)与              解码(Encode).哈弗曼编码是一种数据压缩算              法,以节省数据传输的时间,提高效率。              分为以下四步来完成这项编码              1.Create a Huffman tree for this message.              2.Create a code table.              3.Encode the message into binary.              4.Decode the message from binary back to                text.  Description2:这段代码逻辑正确,测试结果也正确,但仍有一些                 缺陷还没解决。比如编码时出现频率最多的字符编码                 位数要最少,这样得到的编码位数少效率高,这段代码                 并没做到。其次还有对优先级队列运用不是很准确,                 不能精准的控制它.remove出的元素有时不符合我的                 预期。若有有心人的话,可在这个基础上二次开发,                 并将更完善的代码发我一份,共同学习。  *******************************************************/  package main;    import java.util.Comparator;  import java.util.HashMap;  import java.util.PriorityQueue;  import java.util.Set;    public class Main  {      static HashMap<String,Integer> hmNumberTable;    //频率表      static PriorityQueue<HuffmanTree> pqList;    //所有树的队列      static HuffmanTree hTree;    //表示哈夫曼树      static HashMap<String, String> hmCodeTable;    //代码表      static String sHuffman = "";    //Encode的字符串      static String sDecode = "";    //Decode的字符串            public static void main(String[] args)       {          //test word          String sSample = "TODAY IS A GOOD DAY";                    /*一.Create a Huffman tree for this message           */                    //得到每个字符出现几率频率表          hmNumberTable = gethmNumberTable(sSample);                    //定义优先级队列,key值小的排在先          Comparator<HuffmanTree> OrderIsdn =  new Comparator<HuffmanTree>()           {              @Override              public int compare(HuffmanTree o1, HuffmanTree o2)               {                  int numbera = o1.getNumber();                    int numberb = o2.getNumber();                    if(numberb > numbera)                    {                      return -1;                    }                    else if(numberb < numbera)                    {                      return 1;                    }                    else                    {                      return 0;                    }               }          };          pqList = new PriorityQueue<HuffmanTree>(hmNumberTable.size(),OrderIsdn);                    /*操作步骤           *1.为消息中的每个字符创建一个Node对象,每个节点有两个数据项:           *字符和字符在消息中出现的频率。           *2.为这些节点创建tree对象           *3.把这些树都插入到优先级队列pqList当中去,它们按频率排序,           *频率小的有最高优先级。           */          Set<String> sTemp = hmNumberTable.keySet();          for(String string:sTemp)          {              Node node = new Node();              node.cData = string.charAt(0);              node.iNumber = hmNumberTable.get(string);              HuffmanTree hTempTree = new HuffmanTree(node);              pqList.add(hTempTree);          }                    /*操作步骤           *1.从pqList中删除两棵树,并把它们作为一个新节点的子节点。           *新节点的频率是子节点频率的和,它的字符字段可以是空的。           *2.把这个新的三节点树插回优先级队列里。           *3.反复重复第一步和第二步。树会越变越大,队列中的数据项会           *越来越少。当队中只有一颗树时,它就是所建的哈夫曼树了。           */          while(pqList.size() > 1)          {              HuffmanTree hTempA = pqList.peek();              pqList.remove();              HuffmanTree hTempB = pqList.peek();              pqList.remove();              Node node = new Node();              node.cData = '$';    //$作为一个特别的char,用作识别。              node.iNumber = hTempA.getNumber() + hTempB.getNumber();              node.leftChild = hTempA.getRoot();              node.rightChild = hTempB.getRoot();              HuffmanTree hTempC = new HuffmanTree(node);              pqList.add(hTempC);              //测试单元,遍历队列  //            traveQueue(pqList);          }          hTree = pqList.peek();                    /*二.Create a code table.           *得到hmCodeTable           */                    hmCodeTable = new HashMap<String, String>();          getPaths(hTree.getRoot(),"");                    /*三.Encode the message into binary.           */          for(char cTemp:sSample.toCharArray())          {              String string = hmCodeTable.get(String.valueOf(cTemp));              sHuffman = sHuffman + string;          }          System.out.println("Huffman Code:");          System.out.println(sHuffman);                    /*四.Decode the message from binary back to           *     text.           */          int index = 0;          char cIndex;          Node nIndexNode = hTree.getRoot();          while(index < sHuffman.length())          {              cIndex = sHuffman.charAt(index);              if(cIndex == '1')              {                  nIndexNode = nIndexNode.rightChild;              }              else if(cIndex == '0')              {                  nIndexNode = nIndexNode.leftChild;              }              if(nIndexNode.leftChild == null && nIndexNode.rightChild == null)              {                  sDecode = sDecode + nIndexNode.cData;                  nIndexNode = hTree.getRoot();              }              index ++;          }          System.out.println("Decode:");          System.out.println(sDecode);      }            //得到频率的Hash表      private static HashMap<String,Integer> gethmNumberTable(String sSample)       {          HashMap<String,Integer> hmList = new HashMap<String,Integer>();          for(int i = 0;i < sSample.length();i++)          {              char temp = sSample.charAt(i);              String sTemp = String.valueOf(temp);              if(hmList.containsKey(sTemp))              {                  int value = hmList.get(sTemp) + 1;                  hmList.remove(sTemp);                  hmList.put(sTemp, value);              }              else              {                  hmList.put(sTemp,1);              }          }          return hmList;      }            /*递归遍历所有节点,并保存所有叶子节点的路径       *node:父节点       *myPath:父节点本身的路径       *向左走一步为0,向右走一步为1.       *终止条件:遍历到叶子节点为止.因此可遍历完所有叶子节点       *递归代码很简单,但理清思路确花了我好久的时间。       */      private static void getPaths(Node node,String myPath)      {          String[] sPaths = new String[2];          if(node.leftChild == null && node.rightChild == null)          {              System.out.println("{" + node.cData + ":" + myPath + "}");              hmCodeTable.put(String.valueOf(node.cData), myPath);              return;          }          if(node.leftChild != null)          {              sPaths[0] = myPath + "0";              getPaths(node.leftChild,sPaths[0]);          }          if(node.rightChild != null)          {              sPaths[1] = myPath + "1";              getPaths(node.rightChild,sPaths[1]);          }          return;      }            /*UNIT*UNIT       *测试代码        *遍历队列但不删除元素       */      private static void traveQueue(PriorityQueue<HuffmanTree> list)      {          HuffmanTree[] trees = new HuffmanTree[list.size()];          int i = 0;          while(list.size() > 0)          {              HuffmanTree tree = list.peek();              System.out.print(tree.getRoot().cData + ":" + tree.getNumber() + " ");              list.remove();              trees[i] = tree;              i++;          }          System.out.println();          for(HuffmanTree theTree:trees)          {              list.add(theTree);          }      }  }



本站声明:网站内容来源于网络,如有侵权,请联系我们https://www.qiquanji.com,我们将及时处理。

微信扫码关注

更新实时通知

作者:期权小韭菜 分类:网页教程 浏览:
请先 登录 再评论,若不是会员请先 注册