算法#19--霍夫曼压缩（数据压缩）

定义

我们现在来学习一种能够大幅压缩自然语言文件空间（以及许多其他类型文件）的数据压缩技术。

它的主要思想是放弃文本文件的普通保存方式：不在使用7位或8位二进制数表示每一个字符，而是用较少的比特表示出现频率高的字符，用较多的比特表示出现频率低的字符。

简而言之，不在用ASCII编码表示，而是用较短的前缀码表示。

前缀码

什么是前缀码？如果所有字符编码都不会成为其他字符编码的前缀，符合这种规则的叫前缀码。

比如，如果A的编码为0，R的编码为00，那么A的编码是R的前缀，这不属于前缀码。那么前缀码的例子是什么样的呢？如下：

所有的前缀码的解码方式都和它一样，是唯一的。因此前缀码被广泛应用于实际生产中。注意，像7位ASCII编码编码这样的定长编码也是前缀码。

霍夫曼单词查找树

表示前缀码的一种简便方法就是使用单词查找树。

任意含有M个空链接的单词查找树都没M个字符定义了一种前缀码方法：我们将空链接替换为指向叶子结点（含有两个空链接的结点）的链接，每个叶子结点都含有一个需要编码的字符。这样，没个字符的编码都是从根结点到该结点的路径表示的比特字符串，其中左链接表示0，右链接表示1.

如果构造这样一棵树？

首先，树的结点包含left和right，和一个字符频率变量freq，以及字符ch。以下为构造一颗霍夫曼单词查找树的过程：

1. 将需要被编码的字符放在叶子结点中并在每个结点中维护了一个名为freq的实例变量来表示以它为根结点的子树种的所有字符出现的频率。
2. 创建一片由许多只有一个结点（即叶子结点）的树所组成的森林。每棵树都表示输入流的一个字符，每个结点中的freq表示它在输入流中的出现频率。
3. 找到两个频率最小的结点，然后创建一个以二者为子结点的新结点（新结点的频率为它的两个子结点的频率之和）。
4. 不断重复第3过程，最终所有的结点会被合并为一颗单独的单词查找树。

特点：

• 树的叶子结点包含freq和字符。
• 频率高的离根结点最近，频率低的在树的底层。
• 根结点频率值等于输入中的字符数量。
• 该树表示的编码压缩比其他树更多，是一种最优的前缀码

压缩

对于任意单词查找树，都能产生一张将树中的字符和比特字符串（用由0和1组成的String字符串表示）相对应的编译表。其实就是字符和它的比特字符串的符号表。在这里我们用st[]数字表示。在构造符号表时buildCode()递归遍历整棵树，并为每个结点维护一条从根结点到它的路径所对应的二进制字符串（左链接表示0，右链接表示1）。到达一个叶子结点后，就将结点的编码设为该二进制字符串。如下图的编译表：

然后，压缩就很简单了，只需要在其中找到输入字符所对应的编码即可。

上图字符串ABRACADABRA!的编码为：首先是0（A的编码），然后是111（B的编码），然后是110（R的编码），最后得到完整编码为0111110010110100011111001010.

解压

首先readTrie()将霍夫曼单词查找树编码为的比特流构造为霍夫曼查找树。然后读取霍夫曼压缩码，根据该编码从根结点向下移动（读取一个比特，为0移动到左结点，为1移动到右结点）。当遇到叶子结点后，输出该结点的字符并重新回到根结点。

例如压缩ABRACADABRA!后的编码为：0111110010110100011111001010，其单词查找树的比特流为：01010000010010100010001001000011010000110101010010101000010。

首先由树的比特流构造霍夫曼查找树（得如下树），然后解码编码。第一个为0，所以移动到左子结点，输出A；回到根，然后连续三个1，即向右移动3次，输出B；回到根，然后两个1，一个0，即向右移动两次，向左移动一次，输出R。如此重复，最后得到ABRACADABRA!

实现代码

/** * 霍夫曼压缩 * @author nicholas.tang * */
public class Huffman 
{
    public static int R = 256;
    public static final int asciiLength = 8;//ascii码，一个字符等于8个bit
    public static String bitStreamOfTrie = "";//使用前序遍历将霍夫曼单词查找树编码为比特流
    public static int lengthOfText = 0;//要压缩文本的长度

    private static String next = "";//读取霍夫曼单词查找树用到的next字符串，它指向下一个比特流的子字符串，用了遍历比特流

    /** * 霍夫曼单词查找树中的结点 * @author nicholas.tang * */
    private static class Node implements Comparable<Node>
    {
        private char ch;    //内部结点不会使用该变量
        private int freq;   //展开过程不会使用该变量
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right)
        {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public boolean isLeaf()
        {
            return left == null && right == null;
        }

        public int compareTo(Node that)
        {
            return this.freq - that.freq;
        }
    }

    /** * 解压 * @param bitSteam 霍夫曼单词查找树编码为的比特流 * @param length 文本长度 * @param huffmanCode 霍夫曼编码 * @return 解压后的文本 */
    public static String expand(String bitSteam, int length, String huffmanCode)
    {   
        Node root = null;
        if(bitSteam == "")
        {
            return "";
        }
        else
        {
            root = readTrie(bitSteam);  
        }

        int j = 0;
        String text = "";
        for(int i = 0; i while(!x.isLeaf())
            {
                if(huffmanCode.substring(j, j+1).equals("1"))
                {
                    x = x.right;
                }
                else
                {
                    x = x.left;
                }
                j++;
            }
            text +=x.ch;
        }   
        return text;
    }

    /** * 压缩 * @param s 要压缩的文本 * @return 压缩后，反馈的霍夫曼编码 */
    public static String compress(String s)
    {
        //读取输入
        char[] input = s.toCharArray();

        //统计频率
        int[] freq = new int[R];
        for(int i = 0; i //构造霍夫曼编码树
        Node root = buildTrie(freq);

        //递归地构造编译表
        String[] st = new String[R];
        buildCode(st, root, "");

        //递归地打印解码用的单词查找树，即比特流
        writeTrie(root);

        //打印字符总数
        lengthOfText = input.length;

        //使用霍夫曼编码处理输入
        String codeOfHuffman = "";
        for(int i = 0; i for(int j = 0; j if(code.charAt(j) == '1')
                {
                    codeOfHuffman += '1';
                }
                else
                {
                    codeOfHuffman += '0';
                }
            }
        }
        return codeOfHuffman;//返回霍夫曼编码
    }

    /** * 构建霍夫曼单词查找树 * @param freq 字符在文本出现的频率 * @return 霍夫曼单词查找树 */
    private static Node buildTrie(int[] freq)
    {
        MinPQ pq = new MinPQ(R);
        for(char c = 0; c if(freq[c] > 0)
            {
                pq.insert(new Node(c, freq[c], null, null));
            }
        }
        while(pq.size() > 1)
        {//合并两颗频率最小的树
            Node x = pq.delMin();
            Node y = pq.delMin();
            Node parent = new Node('\0', x.freq + y.freq, x, y);
            pq.insert(parent);
        }
        return pq.delMin();
    }

    /** * 构造编译表 * @param st 编译表 * @param x 霍夫曼单词查找树中的结点 * @param s 编译表内容 */
    private static void buildCode(String[] st, Node x, String s)
    {
        if(x.isLeaf())
        {
            st[x.ch] = s;
            return;
        }
        buildCode(st, x.left, s + '0');
        buildCode(st, x.right, s + '1');
    }

    /** * 使用前序遍历将霍夫曼单词查找树编码为比特流 * @param x 霍夫曼单词查找树 */
    private static void writeTrie(Node x)
    {//输出单词查找树的比特字符串
        if(x.isLeaf())
        {
            bitStreamOfTrie += '1';
            String temp = Integer.toBinaryString(x.ch);
            int n = asciiLength - temp.length();
            temp = repeatStrings("0", n) + temp;
            bitStreamOfTrie += temp;
            return ;
        }
        bitStreamOfTrie += '0';
        writeTrie(x.left);
        writeTrie(x.right);
    }   

    /** * 用比特流构造霍夫曼单词查找树 * @param s 比特流 * @return 霍夫曼单词查找树 */
    private static Node readTrie(String s)
    {           
        if(s.substring(0, 1).equals("1"))
        {  
            int value = Integer.parseInt(s.substring(1, 1 + asciiLength),2);
            next = s.substring(1 + asciiLength);
            return new Node((char)value, 0, null, null);            
        }
        else
        {           
            next = s.substring(1);
            return new Node('\0', 0, readTrie(next), readTrie(next));
        }       
    }

    /** * 重复字符串 * @param s 需要重复的字符串 * @param n 重复次数 * @return 重复后的字符串 */
    private static String repeatStrings(String s , int n)
    {
          String temp = "";
          for(int i = 0; i return temp;
    }

    public static void main(String[] args) 
    {
        String text = "ABRACADABRA!";
        System.out.println("Input text: " + text);

        String HuffmanCode = Huffman.compress(text);
        int bitsOfText = Huffman.lengthOfText * Huffman.asciiLength;
        String bitStream = Huffman.bitStreamOfTrie;
        double compressiOnRatio= 1.0 * HuffmanCode.length() / bitsOfText;

        System.out.println("Huffman Code: " + HuffmanCode);     
        System.out.println("BitStream: " + bitStream);
        System.out.println("Huffman Code length(bit): " + HuffmanCode.length());
        System.out.println("Length of text(bit): " + bitsOfText);
        System.out.println("Compression ratio: " + compressionRatio * 100 + "%");

        String expandText = Huffman.expand(bitStream, lengthOfText, HuffmanCode);
        System.out.println("Expand text: " + expandText);
    }
}

输出：

Input text: ABRACADABRA!
Huffman Code: 0111110010110100011111001010
BitStream: 01010000010010100010001001000011010000110101010010101000010
Huffman Code length(bit): 28
Length of text(bit): 96
Compression ratio: 29.166666666666668%
Expand text: ABRACADABRA!