快捷導(dǎo)航

如何用Java實(shí)現(xiàn)啥夫曼編碼

更新時(shí)間：2013年08月14日 10:25:10 作者：

在開(kāi)發(fā)手機(jī)程序時(shí)，總是希望壓縮網(wǎng)絡(luò)傳輸?shù)男畔?，以減少流量。本文僅以哈夫曼編碼為引導(dǎo)，拋磚引玉，實(shí)現(xiàn)壓縮功能

大家可能會(huì)想，程序和第三方提供了很多壓縮方式，何必自己寫(xiě)壓縮代碼呢？不錯(cuò)，如GZIP這樣的壓縮工具很多，可是在某些情況下（如文本內(nèi)容小且字符不重復(fù)），GZIP壓縮后會(huì)比原始文本還要大。所以在某些特殊情況下用自己的壓縮方式可以更優(yōu)。

大家可能早已忘記了在學(xué)校學(xué)習(xí)的哈夫曼知識(shí)，可以先在百度百科了解一下哈夫曼知識(shí)：http://baike.baidu.com/view/127820.htm

哈夫曼思想：統(tǒng)計(jì)文本字符重復(fù)率，求出各字符權(quán)值，再構(gòu)造出一顆最優(yōu)二叉樹(shù)（又稱哈夫曼樹(shù)），然后給每個(gè)葉子結(jié)點(diǎn)生成一個(gè)以位（bit）為單位的碼值，每個(gè)碼值不能做為其他碼值的前綴，再將碼值合并以每8個(gè)生成一個(gè)字節(jié)。

復(fù)制代碼代碼如下:

package com.huffman;

/**
* 結(jié)點(diǎn)
* @author Davee
*/
public class Node implements Comparable<Node> {
    int weight;//權(quán)值
    Node leftChild;//左孩子結(jié)點(diǎn)
    Node rightChild;//右孩子結(jié)點(diǎn)
    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;
    }
}

復(fù)制代碼代碼如下:

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 HashMap<Character, Node> nodeMap;
    private ArrayList<Node> nodeList;

    public HuffmanTree() {
        nodeMap = new HashMap<Character, Node>();
        nodeList = new ArrayList<Node>();
    }

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

    public String decode(Map<String, 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("二進(jìn)制："+sb.toString());

        return sb.toString();
    }

    /**
     * 計(jì)算葉子權(quán)值
     * @param text
     */
    private void calculateWeight(String text) {
        for (Character c : text.toCharArray()) {
            if (nodeMap.containsKey(c)) {
                nodeMap.get(c).increaseWeight(1);//權(quán)值加1
            } else {
                Node leafNode = new Node(c, 1);
                nodeList.add(leafNode);
                nodeMap.put(c, leafNode);
            }
        }
    }

    /**
     * 生成哈夫曼樹(shù)
     * @param nodes
     */
    private Node generateHuffmanTree(ArrayList<Node> 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(ArrayList<Node> 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;//插入到第一個(gè)
        } 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 Map<String, Character> getCodeTable() {
        Map<String, Character> map = new HashMap<String, Character>();
        for (Node node : nodeMap.values()) {
            map.put(node.huffCode, node.value);
        }
        return map;
    }

    /**
     * 打印節(jié)點(diǎn)信息
     * @param root
     */
    private void printNodes(Node root) {
        System.out.println("字符　　權(quán)值　　哈夫碼");
        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);
    }

    /**
     * 打印節(jié)點(diǎn)信息
     * @param nodes
     */
    private void printNodes(ArrayList<Node> nodes) {
        System.out.println("字符　　權(quán)值　　哈夫碼");
        for (Node node : nodes) {
            System.out.println(node.value+"　　　　"+node.weight+"　　　　"+node.huffCode);
        }
    }
}

復(fù)制代碼代碼如下:

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);//測(cè)試
        String binary = huffmanTree.encode(originText);
        byte[] bytes = HuffUtils.binary2Bytes(binary);
        Map<String, Character> codeTable = huffmanTree.getCodeTable();
        int lastByteNum = binary.length() % 8;
        System.out.println(bytes.length);
        //將bytes、codeTable、 lastByteNum傳遞到服務(wù)器端
        //省略。。。。。。

        /*
                         服務(wù)器端解析
                         接收到參數(shù)，并轉(zhuǎn)換成bytes、relationMap、 lastByteNum
        */
        String fullBinary = HuffUtils.bytes2Binary(bytes, lastByteNum);
        System.out.println("服務(wù)器二進(jìn)制："+fullBinary);
        String retrieveText = huffmanTree.decode(codeTable, fullBinary);
        System.out.println("恢復(fù)文本："+retrieveText);
    }
}