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