Huffman Tree

什麼是Huffman coding?

霍夫曼編碼(Huffman Coding)是一種編碼方式，是一種用于無損資料壓縮算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，并發表于《一種建構極小多馀編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。

在電腦資料進行中，霍夫曼編碼使用變長編碼表對源符号（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符号出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字元串的平均長度、期望值降低，進而達到無損壓縮資料的目的。

例如，在英文中，e的出現機率最高，而z的出現機率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位元來表示，而z則可能花去25個位元（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組（byte），即8個位元。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實作對于英文中各個字母出現機率的較準确的估算，就可以大幅度提高無損壓縮的比例。

霍夫曼樹又稱最優二叉樹，是一種帶權路徑長度最短的二叉樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點爲0層，葉結點到根結點的路徑長度爲葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記爲WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N個權值Wi(i=1,2,...n)構成一棵有N個葉結點的二叉樹，相應的葉結點的路徑長度爲Li(i=1,2,...n)。可以證明霍夫曼樹的WPL是最小的。

算法原理：

    ht首先被提出來，是為了解決這樣的問題：

    對于N種資料（比如5種資料：A、B、C、D、E），在出現的頻率已

知的情況下（比如分别出現了3、5、2、6、4次），如何用不等長的01

串來分别表示它們，使01串的總長度最短。

    比如原始串：ABADBCBDABEDBDEDCEDE

    對于這個問題，首先得到：任何一個01串都不能是其他01串的字首

。也就是說，如果用“10”來表示A，那麼其他01串就不能以“10”開

頭。

    建立01串的步驟如下：

    首先找到出現最少的兩個資料（A、C），分别以它們為左右子樹，

建立一個二叉樹。并将它們出現次數之和作為根節點：

1)

    5   5B  6D  4E

   / /

  3A 2C

    然後從剩下的4個數舉重找到兩個最小的，做同上的操作，知道隻

剩一個資料為止：

2)

    5     9    6D

   / /   / /

  3A 2C 5B 4E

3)

      11      9

     /  /    / /

    5   6D  5B 4E

   / /

  3A 2C

4)

           20

          /  /

       11      9

      /  /    / /

     5   6D  5B 4E

    / /

   3A 2C

    最後從根節點開始，每個左子樹填0，右子樹填1：

             ROOT

            /    /

           0      1

          / /    / /

         0  1D  0B 1E

        / /

       0A 1C

    這樣每個資料對應的01串就是從根節點到資料所在的葉子節點的路

徑：

A: 000

B: 10

C: 001

D: 01

E: 11

    這樣原始串ABADBCBDABEDBDEDCEDE就成了：

000100000110001100100010110110011101001110111

通過建Huffman Tree的方法對文本編碼、譯碼

有了上面的算法，使用Huffman編碼的時候就友善了。比如我們要發送ABC，隻要發送00010001就可以了，每個編碼直接都不需要用分割符号。因為解析的時候，諸位提取，對照Huffman編碼進行解析就可以了。比如先讀到0,編碼表裡沒有0，就繼續。然後又讀到0，還沒有找到00，繼續讀，等再次讀到0這個時候就有了一個比對A，然後繼續，就又得到了B和C。

下面是編碼的具體實作：

類BaseNode定義了基本的節點：

public class BaseNode

{

//左節點

public BaseNode Left = null;

//右節點

public BaseNode Right = null;

//權

public int Number = 0;

}

類HuffNode定義了Huffman樹的節點

public class HuffNode : BaseNode

{

//資料

public object Obj = null;

//Huffman編碼

public string Code;

public HuffNode()

{ }

public HuffNode(int number, object obj)

{

Number = number;

Obj = obj;

}

}

下面是Huffman樹的代碼：

public class Huffman

{

//mylist作為Huffman樹隊列

private List<HuffNode> mylist = new List<HuffNode>();

//定義了一個事件，用來處理生成的Huffman編碼

public event EventHandler<NodeEventArgs> OnNodeFound;

//向隊列裡面添加節點

public void Add(HuffNode value)

{

mylist.Add(value);

}

//找到隊列裡面最小的Huffman樹，傳回它，同時從隊列裡面去掉

private HuffNode min()

{

HuffNode anode;

if (mylist.Count > 0)

{

anode = mylist[0];

foreach (HuffNode tempnode in mylist)

{

if (anode.Number > tempnode.Number)

{

anode = tempnode;

}

}

mylist.Remove(anode);

return anode;

}

else

return null;

}

//生成Huffman樹

public void CreateHuffmanTree()

{

HuffNode node = null;

while (mylist.Count > 1)

{

HuffNode tempnode = new HuffNode();

//取得兩個最小的Huffman子樹

tempnode.Left = min();

tempnode.Right = min();

tempnode.Number = tempnode.Left.Number + tempnode.Right.Number;

mylist.Add(tempnode);

}

if (mylist.Count > 0)

node = mylist[0];

//建立Huffman編碼

if (node != null)

{

StringBuilder sb = new StringBuilder();

Stack<HuffNode> stack = new Stack<HuffNode>();

//指向樹根

HuffNode pNow = node;

while (null != pNow)

{

//如果有左子樹，就進入

if (null != pNow.Left)

{

//儲存目前節點

stack.Push(pNow);

//進入左子樹

sb.Append(0);

pNow = pNow.Left as HuffNode;

pNow.Code = sb.ToString();

}

else

{

//沒有左子樹，判斷右子樹

if (null != pNow.Right)

{

//進入右子樹

sb.Append(1);

pNow = pNow.Right as HuffNode;

pNow.Code = sb.ToString();

}

else

{

//是葉子，響應自定義事件，輸出Huffman編碼

NodeEventArgs args = new NodeEventArgs();

args.Node = pNow;

if (OnNodeFound != null)

OnNodeFound(this, args);

//如果堆棧為空，就退出

if (stack.Count == 0)

break;

else

{

pNow = stack.Pop();

sb.Remove(0, sb.Length);

sb.Append(pNow.Code);

//進入這個節點的右子樹

pNow = pNow.Right as HuffNode;

sb.Append(1);

pNow.Code = sb.ToString();

//如果右子樹為空，并且堆棧不空，就繼續

while (null == pNow && stack.Count != 0)

{

pNow = stack.Pop();

pNow = pNow.Right as HuffNode;

}

sb.Remove(0, sb.Length);

if (pNow != null)

sb.Append(pNow.Code);

}

}

}

}

}

}

}

自定義事件參數NodeEventArgs的定義

public class NodeEventArgs : EventArgs

{

public BaseNode Node;

}

測試和使用：

private Huffman huffman = new Huffman();

private void btnHuffman_Click(object sender, EventArgs e)

{

//添加節點

huffman.Add(new HuffNode(120, 'e'));

huffman.Add(new HuffNode(90, 't'));

huffman.Add(new HuffNode(80, 'a'));

huffman.Add(new HuffNode(80, 'i'));

huffman.Add(new HuffNode(80, 'n'));

huffman.Add(new HuffNode(80, 'o'));

huffman.Add(new HuffNode(80, 's'));

huffman.Add(new HuffNode(64, 'h'));

huffman.Add(new HuffNode(62, 'r'));

huffman.Add(new HuffNode(44, 'd'));

huffman.Add(new HuffNode(40, 'l'));

huffman.Add(new HuffNode(34, 'u'));

huffman.Add(new HuffNode(30, 'c'));

huffman.Add(new HuffNode(30, 'm'));

huffman.Add(new HuffNode(25, 'f'));

huffman.Add(new HuffNode(20, 'w'));

huffman.Add(new HuffNode(20, 'y'));

huffman.Add(new HuffNode(17, 'g'));

huffman.Add(new HuffNode(17, 'p'));

huffman.Add(new HuffNode(16, 'b'));

huffman.Add(new HuffNode(12, 'v'));

huffman.Add(new HuffNode(8, 'k'));

huffman.Add(new HuffNode(5, 'q'));

huffman.Add(new HuffNode(4, 'j'));

huffman.Add(new HuffNode(4, 'x'));

huffman.Add(new HuffNode(2, 'z'));

//注冊事件，當生成一個Huffman編碼的時候，就輸出編碼值

huffman.OnNodeFound += new EventHandler<NodeEventArgs>(huffman_OnNodeFound);

//生成Huffman樹

huffman.CreateHuffmanTree();

}

void huffman_OnNodeFound(object sender, NodeEventArgs e)

{

//輸出Huffman編碼

HuffNode node = e.Node as HuffNode;

//如果Obj為空，說明這個節點沒有Huffman編碼，不進行處理

if (node.Obj != null)

System.Console.WriteLine("char:{0} code:{1}",node.Obj.ToString(),node.Code);

}

部分内容轉自 http://blog.csdn.net/schumyxp/archive/2008/04/23/2317183.aspx