浅谈哈夫曼树和哈夫曼编码
在学习二叉树时看到关于哈夫曼编码的一些描述，兴趣来潮，自己写一个算法。哈夫曼算法使用二叉树
以令人惊讶的方式来压缩数据，以提高数据传输的效率和时间。只有知道哈夫曼编码而不会写代码的童鞋们
才会在网上搜代码，故在这里对哈夫曼编码不做过多介绍。
实现哈弗曼(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,我们将及时处理。
微信扫码关注
更新实时通知