哈夫曼编码细解& Java 实现

本文参考: link.
什么是霍夫曼编码

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）
对于哈夫曼编码这种方法实际上核心是用贪心算法来求解的，因为要使编码为不定长的编码，并且还要是能最有效率的解码，那就要使用贪心的策略，
简单来说，若在一个字符串中，知道每个字母各自出现的频率，通过将出现频率较大的字符采用较少位数来编码的方式达到压缩的目的，即一个字符出现的频次越大，它的编码位数应该更少

假设在一个文件中，字符集的频率如下表：

二叉树

分别为a、b、c、d、e、f创建初始化二叉树节点
在列表中寻找根节点中存有最小频率值的两颗二叉树，创建一个不存储任何字符的节点，将这两颗二叉树作为新建节点的左右子树，并将其频次值之和存储到新建节点中。在这6个节点中，频次之和最小的两个是b、c，将左节点的val更新为0，右节点的val更新为1，合并为一个新的二叉树
最终生成的哈夫曼树

public class Huffman {
	//内部类 二叉树节点
    private class TreeNode {
        public TreeNode() { }
        public TreeNode(Character ch, int val, int freq, TreeNode left, TreeNode right) {
            this.ch = ch;
            this.val = val;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }//目的是为了给这个内部类赋值！！！！！！！！！！！！！！！！
        Character ch;
        int val;
        int freq;
        TreeNode left;
        TreeNode right;
    }
	
    @Test
    public void testEncode(){
        String s = "aaabbbeeedacfwwwwddd";

        System.out.println("编码前："+s);

        Object[] encodeRes = encode(s);
        String encodeStr = (String)encodeRes[0];
        Map encodeMap = (Map)encodeRes[1];

        System.out.println("编码表：");
        for(Map.Entry e:encodeMap.entrySet()){
            System.out.println(e.getKey()+":"+e.getValue());
        }
        System.out.println("编码后："+encodeStr);

        String decodeStr = decode(encodeStr,encodeMap);
        System.out.println("解码后:"+decodeStr);
    }
	
	//编码方法，返回Object[]，大小为2,Objec[0]为编码后的字符串，Object[1]为编码对应的码表
    public Object[] encode(String s){
        Object[]res= new Object[2];  
        //object是所有类的父类，何一个类时候如果没有明确的继承一个父类的话，那么它就是Object的子类；
        Map encodeMap = new HashMap();
        TreeNode tree = constructTree(s);
        findPath(tree, encodeMap, new StringBuilder());
        findPath(tree, encodeMap, new StringBuilder());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i dataMap = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (dataMap.containsKey(c)) {
                int count = dataMap.get(c);
                dataMap.put(c, count + 1);
            } else {
                dataMap.put(c, 1);
            }
        }
        //遍历dataMap,初始化二叉树节点，并将所有初始化后的节点放到nodeList中，并进行排序
        linkedList nodeList = new linkedList();
        for (Map.Entry entry : dataMap.entrySet()) {
            Character ch = entry.getKey();
            int freq = entry.getValue();
            int val = 0;
            TreeNode tmp = new TreeNode(ch,val,freq,null,null);
            nodeList.add(tmp);
        }
		//对存放节点的链表进行排序，方便后续进行组合
        Collections.sort(nodeList, new Comparator() {
            public int compare(TreeNode t1, TreeNode t2) {
                return t1.freq-t2.freq;
            }
        });

        //size==1,代表字符串只包含一种类型的字母
        if(nodeList.size()==1){
            TreeNode t = nodeList.get(0);
            return new TreeNode(null,0,nodeList.get(0).freq,t,null);
        }

        //利用排序好的节点建立二叉树，root为初始化根节点
        TreeNode root = null;
        while(nodeList.size()>0){
			//因为nodeList在前面已经排好序，所以直接取出前两个节点，他们的和肯定为最小
            TreeNode t1 = nodeList.removeFirst();
            TreeNode t2 = nodeList.removeFirst();
			//左子树的val赋值为0，右子树的val赋值为1
            t1.val = 0;
            t2.val = 1;
			//将取出的两个节点进行合并
            if(nodeList.size()==0){
				//此时代表所有节点合并完毕，返回结果
                root = new TreeNode(null,0,t1.freq+t2.freq,t1,t2);
            }else {
				//此时代表还有可以合并的节点
                TreeNode tmp = new TreeNode(null,0,t1.freq+t2.freq,t1,t2);
				
                //t1、t2合并后，需要将得到的新节点加入到原链表中，继续与其他节点合并，
				//此时需要保证原链表的有序性，需要进行排序
                if(tmp.freq>nodeList.getLast().freq){
                    nodeList.addLast(tmp);
                }else {
                    for(int i=0;i res, StringBuilder path) {
        if (root.left == null && root.right == null) {
            path.append(root.val);
            res.put(root.ch,path.substring(1));
            path.deleteCharAt(path.length() - 1);
            return;
        }
        path.append(root.val);
        if (root.left != null) findPath(root.left, res, path);
        if (root.right != null) findPath(root.right, res, path);
        path.deleteCharAt(path.length() - 1);
    }
	
	//对字符串进行解码，解码时需要编码码表
	public String decode(String encodeStr,Map encodeMap){
        StringBuilder decodeStr = new StringBuilder();
        while(encodeStr.length()>0){
            for(Map.Entry e: encodeMap.entrySet()){
                String charEncodeStr = e.getValue();
                if(encodeStr.startsWith(charEncodeStr)){
                    decodeStr.append(e.getKey());
                    encodeStr = encodeStr.substring(charEncodeStr.length());
                    break;
                }
            }
        }
        return decodeStr.toString();
    }
	
}

编码前：aaabbbeeedacfwwwwddd
编码表：
a:111
b:101
c:1000
d:00
e:110
f:1001
w:01
编码后：111111111101101101110110110001111000100101010101000000
解码后:aaabbbeeedacfwwwwddd

Object类是Javajava.lang包下的核心类，Object类是所有类的父类，何一个类时候如果没有明确的继承一个父类的话，那么它就是Object的子类；

相当于告诉我们，当我们遇到object类时候，都可以把它当做一般的类来对待

1. clone()
   保护方法，实现对象的浅复制，只有实现了Cloneable接口才可以调用该方法，否则抛出CloneNotSupportedException异常。
2. getClass()
   final方法，返回Class类型的对象，反射来获取对象。
3. toString()
   该方法用得比较多，一般子类都有覆盖，来获取对象的信息。
4. finalize()
   该方法用于释放资源。因为无法确定该方法什么时候被调用，很少使用。
5. equals()
   比较对象的内容是否相等
6. hashCode()
   该方法用于哈希查找，重写了equals方法一般都要重写hashCode方法。这个方法在一些具有哈希功能的Collection中用到。
7. wait()
   wait方法就是使当前线程等待该对象的锁，当前线程必须是该对象的拥有者，也就是具有该对象的锁。wait()方法一直等待，直到获得锁或者被中断。wait(long timeout)设定一个超时间隔，如果在规定时间内没有获得锁就返回。
   调用该方法后当前线程进入睡眠状态，直到以下事件发生。
   其他线程调用了该对象的notify方法。
   其他线程调用了该对象的notifyAll方法。
   其他线程调用了interrupt中断该线程。
   时间间隔到了。
   此时该线程就可以被调度了，如果是被中断的话就抛出一个InterruptedException异常。
8. notify()
   该方法唤醒在该对象上等待的某个线程。
9. notifyAll()
   该方法唤醒在该对象上等待的所有线程。

toString( )
equals()