霍夫曼编码和解码

编码步骤：
1、准备待编码的字符串(可以从文本文件中读取不包含中文)。
2、统计字符串中每个字符出现的次数。(设置一个长度为256的数组，使用字符对应的ASCII码作为数组下标，保存次数。如：array[‘a’]=10;表示字符a出现10次。)
3、根据上面的数组，生成节点。(每个字符对应一个节点，以链表形式链接起来，同时链表按从小到大排序。)
4、构造霍夫曼树。每次删除链表中的两个节点，生成一个新节点。并将这个节点重新插入到链表合适位置。(构造霍夫曼树参考：打开)。霍夫曼树解码时需要使用。
5、通过前序遍历，求出每个字符的二进制编码。同样设置一个长度为256的数组，下标为字符对应的ASCII码。没出现的字符编码为null，不考虑。
6、根据求出的二进制编码替换原来的每个字符。得到整个字符串对应的二进制编码。
7、将二进制编码按照每8位生成一个新字符。最后剩的不足8位的在后面补上count个0，计算一个新字符。补0的个数解码时需要使用。
8、将这些生成的新字符替换掉二进制编码字符串，即可得到编码后的内容。长度将在一定程度上变短。

public class Node { // 既是树的节点也是链表的节点
    public int data; // 存的字符0-255
    public int weight;
    public Node lchild;
    public Node rchild;
    public Node next; // 用于链表

    public Node(int d, int w) {
        data = d;
        weight = w;
        lchild = rchild = next = null;
    }
}

public class HuffmanCode {

    public static int count = 0;
    public static Node head = null;

    public static void main(String[] args) {
        String t = code("youareagoodboy");
        String r = decode(t);
        System.out.println(r);
    }

    // 对任意字符串进行霍夫曼编码
    public static String code(String str) {
        // 根据字符串中不同字符出现次数作为权值构造霍夫曼树
        // 根据霍夫曼树求出每个字符的对应编码
        // 根据编码将原字符串生成编码串
        int[] n = new int[256]; // 使用ASCII码确定每个字符出现的次数
        int i;
        for(i=0; i<256; i++) {
            n[i] = 0;
        }

        int len = str.length();
        char c;
        for(i=0; i<len; i++) { // 求次数
            c = str.charAt(i);
            n[c]++;
        }

        // 构造一个单向链表，从小到大顺序排列森林中的树
        Node t, p, pp;
        for(i=0; i<256; i++) {
            if(n[i] != 0) { //(char)i必须出现过
                t = new Node(i, n[i]);
                if(head == null) {
                    head = t;
                } else {
                    if(t.weight < head.weight) { // 新节点插在首位
                        t.next = head; // 该节点指向头节点
                        head = t; // 头指针指向它
                    } else {
                        // 按顺序加入链表
                        pp = head;
                        p = head.next;
                        while(p != null) {
                    // 新节点权值较小，放在旧节点前面      
                    if(t.weight < p.weight) { 
                                pp.next = t;
                                t.next = p;
                                break;
                            } else {
                                pp = p;
                                p = p.next;
                            }
                        }
                        // 在结尾插入
                        if(p == null && pp != null) {
                            pp.next = t;
                        }
                    }
                }
            }
        }

        // 根据这个单向链表森林，构造霍夫曼树
        Node min1, min2;
        Node newNode;
        while(head.next != null) { // 当森林有超过一棵树时
            min1 = head;
            min2 = head.next;
            newNode = new Node(256, min1.weight+min2.weight);
            newNode.rchild = min2;
            newNode.lchild = min1;
            // 删除原来两棵树
            head = min2.next;
            // 将新树加进去
            if(head == null) {
                head = newNode;
            } else {
                if(newNode.weight < head.weight) { // 新节点插在首位
                    newNode.next = head; // 该节点指向头节点
                    head = newNode; // 头指针指向它
                } else {
                    // 按顺序加入链表
                    pp = head;
                    p = head.next;
                    while(p != null) {
                        if(newNode.weight < p.weight) { // 新节点权值较小，放在旧节点前面
                            pp.next = newNode;
                            newNode.next = p;
                            break;
                        } else {
                            pp = p;
                            p = p.next;
                        }
                    }
                    // 在结尾插入
                    if(p == null && pp != null) {
                        pp.next = newNode;
                    }
                }
            }
        }

        // 霍夫曼树构造完毕，求出对应编码，head为树根节点
        String[] bianma = new String[256];
        for(i=0; i<256; i++) {
            bianma[i] = null;
        }
        preOrder(head, bianma, "");

        // 使用编码替换原来的文本
        String result = "";
        for(i=0; i<len; i++) {
            result += bianma[str.charAt(i)];
        }

        // 将编码每8位转化成一个ASCII码字符
        String s;
        int m = 1;
        int j;
        int r;
        String real = "";
        while(result.length() >= 8) {
            r = 0;
            m = 1;
            s = result.substring(0, 8);

            result = result.substring(8);
            for(j=7; j>=0; j--) {
                r += (s.charAt(j)-'0')*m;
                m *= 2;
            }
            real += (char)r;
        }
        count = 8 - result.length(); // 补0的个数
        for(j=0; j<count; j++) {
            result += '0';
        }
        r = 0;
        m = 1;
        for(j=7; j>=0; j--) {
            r += (result.charAt(j)-'0')*m;
            m *= 2;
        }
        real += (char)r;

        return real;
    }

    public static void preOrder(Node head, String[] bianma, String str) {
        if(head.rchild == null && head.lchild == null) {
            bianma[head.data] = str;
            return;
        }
        str += "0";
        preOrder(head.lchild, bianma, str);
        str = str.substring(0, str.length() - 1);
        str += "1";
        preOrder(head.rchild, bianma, str);
        str = str.substring(0, str.length() - 1);
    }

    // 根据霍夫曼树对给定字符串解码
    public static String decode(String str) {
        char[] c = str.toCharArray();
        String result = "";

        String b;
        int t;
        // 将每个字符转化成8位二进制串
        for(int i=0; i<c.length; i++) { 
            b = "";
            t = c[i];
            while(t != 0) {
                b = (t%2) + b;
                t /= 2;
            }
            while(b.length() < 8) { // 不够8位补零
                b = '0' + b;
            }

            result += b; // 原来的二进制串
        }

        int len = result.length()-count; // 真实二进制字符串长度需要去除补得0
        String real = "";
        Node p = head;

        for(int i=0; i<len; i++) {
            if(p.data == 256) {
                if(result.charAt(i) == '0') {
                    p = p.lchild;
                } else {
                    p = p.rchild;
                }
                if(p.data != 256) { // 走到叶子点，找到对应字符
                    real += (char)p.data;
                    p = head;
                }
            }
        }
        return real;
    }

}

注意：本代码对ASCII码内字符适用。因为其他字符(无论采用哪种编码)超过一个字节，计数和统计编码的数组下标将越界。