Huffman codes

簡介

    在很早以前的時候有學習過huffman編碼，憑借當年的一點學習的印象隻是知道它是一種有效的存儲和壓縮資料的方式。至于這種編碼背後的思路是什麼，它為什麼能帶來有效的編碼壓縮效果都沒有深究。這裡結合最近學習的一點感悟做一步的讨論。

Huffman編碼的引入

    在詳細介紹huffman編碼之前，我們可以先考慮一個典型的字元編碼和存儲的場景。假定有一個含有100000個字元的檔案，它裡有很多個字元。我們經過統計之後發現出現的字元主要有6個，分别為a, b, c, d, e, f。他們出現的頻率如下表所示：

a	b	c	d	e	f
出現頻率	45000	13000	12000	16000	9000	5000
編碼	000	001	010	011	100	101

    因為我們知道一個字元存儲需要兩個位元組，而我們這裡需要對字元進行壓縮，是以希望能用盡可能少的位元組來表示他們。而為了盡可能簡潔的來表達這些字元，對于這6個元素來說，我們可以采用3個位來表示他們。是以這裡a到f分别用000到101表示。如前面表所示。按照這種做法，我們發現這種編碼方式生成的檔案占用空間大小為100000 * 3 bit = 300000bit。和前面100000 * 2byte = 200000 byte比起來，确實有比較大的壓縮效果改進。

改進

    前面的編碼方式看起來已經有了不小的進步。我們還有沒有改進的空間呢？我們來看前面選擇編碼的思路。因為我們總共有6個字元，如果用2進制來表示的話，至少要3個位，是以就采用了3個。這裡考慮僅僅是有多少個字元要表示。這是一個方面。可是，我們忽略了另外一個方面。在檔案裡，每個字元有它出現的頻率，比如a出現的頻率最高，f出現的頻率最低。有沒有可能我們讓出現頻率越高的字元盡量短，而出現頻率低的字元可以稍微長一點呢？比如前面的示例中，我們是所有字元的長度都是平均的3位，如果我們對于頻率最高的那個字元直接用一個位來描述，這樣豈不是更省空間？比如前面字元a出現了45000次，如果我們隻是用一個位來表示它的話，則省下了90000個位。當然，對于這一步來說它确實是省到了。如果按照這個思路來，我們後續的字元該怎麼編碼呢？我們需要用沒有歧義的編碼來表示這些字元。而前面第一種方法所能表示的極限就是3個位。如果這裡我們直接就用去了一個位，要表示後面5個元素，會不會導緻某些元素要使用更多的位呢？

    其實，這就是huffman裡面采取的一個政策。我們充分利用統計的結果，将頻率高的字元編碼盡可能設的短，而頻率低的設的稍微長一些。因為頻率高的帶來的空間節約比頻率低帶來的空間消耗要多，是以能夠實作更進一步的空間壓縮。比如說，我們在前面的問題裡，假定有3個字元要編碼。按照我們剛才的情況，a已經占用了字元0,而另外兩個字元隻能是10, 11了。他們的編碼情況如下圖：

    這裡，a的編碼是0, b的編碼是10，c的編碼是11。和前面那種按字元編碼的方式來說，這種方式确實做到了某些字元很短，帶來的代價是某些字元的編碼會變得長一些。這裡，我們難免會有另外一個問題。為什麼我們要這樣來編碼，不能把b編碼成00, c編碼成01嗎？

    在這裡，如果按照這種方式編碼的話是不合理的。因為我們要考慮到編碼以後要解碼時的問題。如果a編碼成0，b編碼成00，c編碼成01了。我們碰到一組01串如001010時，這會兒編碼就會産生歧義，我們是應該将第一個0解析成a呢還是将前面兩個0解析成b呢？是以，為了更加高效率的解析這些字元，我們必須保證一個字元的編碼不是另外一個字元編碼的字首。

    以我們前面讨論的示例為基礎，基于字元數量和字元頻率編碼的這兩種思路，産生的編碼結果比較如下圖：

    如果我們詳細計算按照後面這種編碼方式占用的空間的話，後面這種的位數為: 224000。

Huffman樹的構造

    前面示例中隻是展示了一個huffman編碼的結果，具體的huffman樹該如何構造呢？按照我們前面讨論的思路，越頻繁的字元編碼越短。反過來說，出現次數越少的字元編碼越長。我們可以倒過來，從葉節點來構造整棵樹。

    我們首先選擇頻率最低的兩個節點，然後将他們歸并到一個節點下。這個新構造的節點的頻率為兩個子節點的頻率之和。然後将這個新生成加入到取出了兩個子節點的集合中，再重複原來的過程。這樣我們就得到最終的huffman樹。以前面的示例來考慮，我們這6個節點中，頻率最低的是e和f。我們第一步則構造一個合并它們兩個的節點，如下圖：

    這裡的一個要點是我們新構造的這個節點，它的頻率為e和f頻率的和。我們将這個節點當作一個字元加入到原來的集合裡，然後再按照前面的過程來選取頻率最低的兩個：

    按照這個過程，後面的流程如下：

    現在，我們已經知道怎麼來構造huffman樹了。我們從具體實作的角度來看看。

    我們這裡的要點是每次選擇最小的兩個元素，然後将他們歸并到一個新節點下。而新節點的頻率值為兩個節點的和。那麼，我們是不是需要将這些元素都排序呢？如果我們排序的話，可能需要O(nlgn)的時間。但是我們每次移除了兩個最小元素之後又要将他們的和加入到集合中來，這樣就破壞了原來的順序性。看來直接排序然後拿過來用的效果并不理想。這個時候，如果我們回想起以前用的資料結構堆來，會發現它是解決這個問題的一個理想選擇。

實作讨論

    我們建一個堆花費的時間為O(n)，比排序要好一些。另外，每次取兩個最小的元素，是以應該是一個最小堆。将新構造的元素加入到堆中，之需要堆做一個調整，時間複雜度為O(lgn)。看來整體情況确實很理想。關于堆和最小堆的分析，可以參考我前面的堆排序這篇文章和priority queue這篇文章。

    我們這裡既然是用的最小堆，那完全可以直接使用最小堆來儲存所有這些元素。另外，這些元素要構成一個huffman樹，我們需要定義每個元素成一個樹節點的樣式。感覺這裡是最小堆和二叉樹的結合。

    根據這裡的讨論，下面是一個參考實作：

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

public class Huffman {

    public static class Node implements Comparable<Node> {
        private int freq;
        private char c;
        private Node left;
        private Node right;

        public Node(int freq, char c) {
            this.freq = freq;
            this.c = c;
        }

        public Node(int freq) {
            this.freq = freq;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getFreq() {
            return freq;
        }

        @Override
        public int compareTo(Node node) {
            return this.freq - node.getFreq();
        }
    }

    public Node encode(List<Node> list) {
        PriorityQueue<Node> queue = new PriorityQueue<Node>(list);
        for(int i = 0; i < list.size() - 1; i++) {
            Node x = queue.poll();
            Node y = queue.poll();
            Node z = new Node(x.getFreq() + y.getFreq());
            z.setLeft(x);
            z.setRight(y);
            queue.add(z);
        }
        return queue.poll();
    }

    public void printEncodedTree(Node node) {
        if(node != null) {
            System.out.println(node.getFreq() + " ");
            printEncodedTree(node.getLeft());
            printEncodedTree(node.getRight());
        }
    }

    public static void main(String[] args) {
        Huffman huffman = new Huffman();
        List<Node> list = new ArrayList<Node>();
        list.add(new Node(45, 'a'));
        list.add(new Node(13, 'b'));
        list.add(new Node(12, 'c'));
        list.add(new Node(16, 'd'));
        list.add(new Node(9, 'e'));
        list.add(new Node(5, 'f'));
        Node node = huffman.encode(list);
        System.out.println(node.getFreq());
        huffman.printEncodedTree(node);
    }
}
           

    這部分代碼看起來比較長，主要是充分利用了jdk類庫裡現有的PriorityQueue。當然，如果我們有興趣也可以參考我前面關于堆的文章自己來實作一個。另外，這部分代碼裡一個比較有意思的地方就是我們定義的節點Node必須是可以比較的。因為我們從前面的讨論裡也看到，我們每次要挑選最小的元素出來，怎麼挑呢？肯定需要比較。是以這裡采用一種實作Comparable接口的方法。當然，關于怎麼使用PriorityQueue，可以參考後續的文檔。代碼中還有一個有意思的地方就是在encode方法裡，我們是循環周遊n-1次，這樣最後PriorityQueue裡剩下一個元素，這個元素就是我們要構造出來的樹的根節點。

    為了能夠看到整個樹的結果，這裡用一個簡單的前序周遊方法列印出來了每個節點的頻率值。

前面程式運作的結果如下：

100
100 
45 
55 
25 
12 
13 
30 
14 
5 
9 
16 
           

    前面程式實作的是huffman編碼。如果我們還需要解碼，該怎麼來做呢？這裡我們也做一個簡單的概括，代碼再後續補上。因為這裡編碼的每個字元都是唯一的。我們可以每次讀進一個數字的時候就對應在樹裡周遊一步。比如說目前讀到的是0,則轉向左子節點，否則到右子節點。如果這個時候發現已經到葉節點了，這個時候可以将這幾個數字編碼對應的字元輸出。我們可以用一個HashMap來事先儲存好他們之間的映射關系。這樣每次周遊到一個葉節點構成一個數字序列時我們可以直接取出對應的字元來。

總結

    Huffman編碼其實本質上并不複雜。它的背後也有一種貪心算法的思路。我們在确定一個頻率越高編碼越短的前提之後，每次盡量将頻率低的放到長一點的葉節點上。具體關于它們為什麼是最優的，我們可以參考書上面的證明，這裡就不再贅述了。

參考材料

Introduction to algorithms

http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue