如何用Java实现啥夫曼编码

【 tulaoshi.com - 编程语言 】

大家可能会想，程序和第三方提供了很多压缩方式，何必自己写压缩代码呢？不错，如GZIP这样的压缩工具很多，可是在某些情况下（如文本内容小且字符不重复），GZIP压缩后会比原始文本还要大。所以在某些特殊情况下用自己的压缩方式可以更优。

大家可能早已忘记了在学校学习的哈夫曼知识，可以先在百度百科了解一下哈夫曼知识：http://baike.baidu.com/view/127820.htm

哈夫曼思想：统计文本字符重复率，求出各字符权值，再构造出一颗最优二叉树（又称哈夫曼树），然后给每个叶子结点生成一个以位（bit）为单位的码值，每个码值不能做为其 他码值的前缀，再将码值合并以每8个生成一个字节。
代码如下：

package com.huffman;

/**
 * 结点
 * @author Davee
 */
public class Node implements ComparableNode {
    int weight;//权值
    Node leftChild;//左孩子结点
    Node rightChild;//右孩子结点
    String huffCode;
    private boolean isLeaf;//是否是叶子
    Character value;

    public Node(Character value, int weight) {
        this.value = value;
        this.weight = weight;
        this.isLeaf = true;
    }

    public Node(int weight, Node leftChild, Node rightChild) {
        this.weight = weight;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    public void increaseWeight(int i) {
        weight += i;
    }

    public boolean isLeaf() {
        return isLeaf;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

代码如下：

package com.huffman;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class HuffmanTree {
    private boolean debug = false;

    private HashMapCharacter, Node nodeMap;
    private ArrayListNode nodeList;

    public HuffmanTree() {
        nodeMap = new HashMapCharacter, Node();
        nodeList = new ArrayListNode();
    }

    public void setDebug(boolean debug) {
        this.debug = debug;
    }

    public String decode(MapString, Character codeTable, String binary) {
        int begin = 0, end = 1, count = binary.length();
        StringBuffer sb = new StringBuffer();
        while (end = count) {
            String key = binary.substring(begin, end);
            if (codeTable.containsKey(key)) {
                sb.append(codeTable.get(key));
                begin = end;
            } else {
            }
            end++;
        }
        return sb.toString();
    }

    public String encode(String originText) {
        if (originText == null) return null;

        calculateWeight(originText);

//        if (debug) printNodes(nodeList);

        Node root = generateHuffmanTree(nodeList);

        generateHuffmanCode(root, "");

        if (debug) printNodes(root);

        StringBuffer sb = new StringBuffer();
        for (Character key : originText.toCharArray()) {
            sb.append(nodeMap.get(key).huffCode);
        }
        if (debug) System.out.println("二进制："+sb.toString());

        return sb.toString();
    }

    /**
     * 计算叶子权值
     * @param text
     */
    private void calculateWeight(String text) {
        for (Character c : text.toCharArray()) {
            if (nodeMap.containsKey(c)) {
                nodeMap.get(c).increaseWeight(1);//权值加1
            } else {
                Node leafNode = new Node(c, 1);
                nodeList.add(leafNode);
                nodeMap.put(c, leafNode);
            }
        }
    }

    /**
     * 生成哈夫曼树
     * @param nodes
     */
    private Node generateHuffmanTree(ArrayListNode nodes) {
        Collections.sort(nodes);
        while(nodes.size() 1) {
            Node ln = nodes.remove(0);
            Node rn = nodes.remove(0);
            insertSort(nodes, new Node(ln.weight + rn.weight, ln, rn));
        }
        Node root = nodes.remove(0);
        nodes = null;
        return root;
    }

    /**
     * 插入排序
     * @param sortedNodes
     * @param node
     */
    private void insertSort(ArrayListNode sortedNodes, Node node) {
        if (sortedNodes == null) return;

        int weight = node.weight;
        int min = 0, max = sortedNodes.size();
        int index;
        if (sortedNodes.size() == 0) {
            index = 0;
        } else if (weight sortedNodes.get(min).weight) {
            index = min;//插入到第一个
        } else if (weight = sortedNodes.get(max-1).weight) {
            index = max;//插入到最后
        } else {
            index = max/2;
            for (int i=0, count=max/2; i=count; i++) {
                if (weight = sortedNodes.get(index-1).weight && weight sortedNodes.get(index).weight) {
                    break;
                } else if (weight sortedNodes.get(index).weight) {
                    max = index;
                } else {
                    min = index;
                }
                index = (max + min)/2;
            }
        }
        sortedNodes.add(index, node);
    }

    private void generateHuffmanCode(Node node, String code) {
        if (node.isLeaf()) node.huffCode = code;
        else {
            generateHuffmanCode(node.leftChild, code + "0");
            generateHuffmanCode(node.rightChild, code + "1");
        }
    }

    /**
     * 生成码表
     * @return
     */
    public MapString, Character getCodeTable() {
        MapString, Character map = new HashMapString, Character();
        for (Node node : nodeMap.values()) {
            map.put(node.huffCode, node.value);
        }
        return map;
    }

    /**
     * 打印节点信息
     * @param root
     */
    private void printNodes(Node root) {
        System.out.println("字符　　权值　　哈夫码");
        printTree(root);
    }

    private void printTree(Node root) {
        if (root.isLeaf()) System.out.println((root.value == null ? "   " : root.value)+"　　　　"+root.weight+"　　　　"+(root.huffCode == null ? "" : root.huffCode));
        if (root.leftChild != null) printTree(root.leftChild);
        if (root.rightChild != null) printTree(root.rightChild);
    }

    /**
     * 打印节点信息
     * @param nodes
     */
    private void printNodes(ArrayListNode nodes) {
        System.out.println("字符　　权值　　哈夫码");
        for (Node node : nodes) {
            System.out.println(node.value+"　　　　"+node.weight+"　　　　"+node.huffCode);
        }
    }
}

代码如下：

package com.test;

import java.util.Map;

import com.huffman.HuffUtils;
import com.huffman.HuffmanTree;

public class Test {
    public static void main(String[] args) {
        String originText = "abcdacaha";
        HuffmanTree huffmanTree = new HuffmanTree();
        huffmanTree.setDebug(true);//测试
        String binary = huffmanTree.encode(originText);
        byte[] bytes = HuffUtils.binary2Bytes(binary);
        MapString, Character codeTable = huffmanTree.getCodeTable();
        int lastByteNum = binary.length() % 8;
        System.out.println(bytes.length);
        //将bytes、codeTable、 lastByteNum传递到服务器端
        //省略。。。。。。

        /*
                         服务器端解析
                         接收到参数，并转换成bytes、relationMap、 lastByteNum
        */
        String fullBinary = HuffUtils.bytes2Binary(bytes, lastByteNum);
        System.out.println("服务器二进制："+fullBinary);
        String retrieveText = huffmanTree.decode(codeTable, fullBinary);
        System.out.println("恢复文本："+retrieveText);
    }
}