霍夫曼編碼

霍夫曼編碼演演算法。由美國電腦科學家大衛·霍夫曼中發表了這個編碼方法。一組符號。一組二元的前置碼，其二元碼的長度為最短。符號集合formula_1，其S集合的大小為formula_2。權重集合formula_3，其W集合不為負數且formula_4。一組編碼formula_5，其C集合是一組二進位制編碼且formula_6為formula_7相對應的編碼，formula_8。設formula_9為formula_10的加權的路徑長，對所有編碼formula_11，則formula_12問題定義與解法.範例.霍夫曼樹常處理符號編寫工作。根據整組資料中符號出現的頻率高低，決定如何給符號編碼。如果符號出現的頻率越高，則給符號的碼越短，相反符號的號碼越長。假設我們要給一個英文單字"F O R G E T"進行霍夫曼編碼，而每個英文字母出現的頻率分別列在"Fig.1"。演算過程.進行霍夫曼編碼前，我們先建立一個霍夫曼樹。⒈將每個英文字母依照出現頻率由小排到大，最小在左，如"Fig.1"。⒉每個字母都代表一個終端節點，比較F.O.R.G.E.T六個字母中每個字母的出現頻率，將最小的兩個字母頻率相加合成一個新的節點。如"Fig.2"所示，發現F與O的頻率最小，故相加2+3=5。⒊比較5.R.G.E.T，發現R與G的頻率最小，故相加4+4=8。⒋比較5.8.E.T，發現5與E的頻率最小，故相加5+5=10。⒌比較8.10.T，發現8與T的頻率最小，故相加8+7=15。⒍最後剩10.15，沒有可以比較的物件，相加10+15=25。最後產生的樹狀圖就是霍夫曼樹，參考"Fig.2"。進行編碼1.給霍夫曼樹的所有左鏈結'0'與右鏈結'1'。2.從樹根至樹葉依序記錄所有字母的編碼，如"Fig.3"。實現方法.資料壓縮.實現霍夫曼編碼的方式主要是建立一個二元樹和其節點。這些樹的節點可以儲存在陣列裡，陣列的大小為符號。一開始，所有的節點都是終端節點，節點內有三個欄位：1.符號2.權重3.指向父節點的鏈結而非終端節點內有四個欄位：1.權重2.指向兩個子節點的鏈結3.指向父節點的鏈結基本上，我們用'0'與'1'分別代表指向左子節點與右子節點，最後為完成的二元樹共有n個終端節點與n-1個非終端節點，去除了不必要的符號並產生最佳的編碼長度。過程中，每個終端節點都包含著一個權重，兩兩終端節點結合會產生一個新節點，新節點的權重是由兩個權重最小的終端節點權重之總和，並持續進行此過程直到只剩下一個節點為止。實現霍夫曼樹的方式有很多種，可以使用優先佇列，演演算法如下：⒈把n個終端節點加入優先佇列，則n個節點都有一個優先權Pi，1 ≤ i ≤ n⒉如果佇列內的節點數&gt;1，則：⑴從佇列中移除兩個最小的Pi節點，即連續做兩次remove, Priority_Queue)⑵產生一個新節點，此節點為兩節點之權重和⑶把產生之節點加入優先佇列中⒊最後在優先佇列裡的點為樹的根節點而此演演算法的時間複雜度。此外，有一個更快的方式使時間複雜度降至線性時間權重永遠都是最小值，且方法如下：⒈把n個終端節點加入第一個佇列⒉如果佇列內的節點數&gt;1，則：⑴從佇列前端移除兩個最低權重的節點⑵將中移除的兩個節點權重相加合成一個新節點⑶加入第二個佇列⒊最後在第一個佇列的節點為根節點雖然使用此方法比使用優先佇列的時間複雜度還低，但是注意此法的第1項，節點必須依照權重大小加入佇列中，如果節點加入順序不按大小，則需要經過排序，則至少花了O的時間複雜度計算。但是在不同的狀況考量下，時間複雜度並非是最重要的，如果我們今天考慮英文字母的出現頻率，變數n就是英文字母的26個字母，則使用哪一種演演算法時間複雜度都不會影響很大，因為n不是一筆龐大的數字。資料解壓縮.簡單來說，霍夫曼碼樹的解壓縮就是將得到的前置碼一步一步還原。但是要追蹤樹之前，必須要先重建霍夫曼樹；某些情況下，如果每個符號的權重可以被事先預測，那麼霍夫曼樹就可以預先重建，並且儲存並重複使用，否則，傳送端必須預先傳送霍夫曼樹的相關資訊給接收端。最簡單的方式，就是預先統計各符號的權重並加入至壓縮之位元串，但是此法的運算量花費相當大，並不適合實際的應用。若是使用Canonical encoding，則可精準得知樹重建的資料量只佔"B"2^"B"位元，則霍夫曼樹則可被重建，以此方法，資料量的大小可能為2~320位元組不等。雖然還有很多方法可以重建霍夫曼樹，但因為壓縮的資料串包含"trailing bits"，所以還原時一定要考慮何時停止，不要還原到錯誤的值，如在資料壓縮時時加上每筆資料的長度等。基本性質.考量到不同的應用領域以及該領域的平均性質，將會使用不同的通用機率，又或者，這個機率是可以從被壓縮文字中的實際頻率所取得。最佳化.原始的霍夫曼演演算法是一個符號與符號間已知輸入機率分佈的最佳編碼方式，也就是說將不相關的符號個別編碼為如此的資料串流。然而，當符號間的限制被捨棄或是質量機率函式是未知的時候，如此方式則並非最佳化。此外，當這些符號之間不是互相獨立，且分佈不相同的時候，單一一個符號可能不足以實現最佳化。在這種情況之下，算術編碼可能比起霍夫曼編碼會有更佳的壓縮能力。雖然上述兩種方法都可以組合任意數量的符號以實現更高效的編碼效果，並且通常適應於實際的輸入統計層面，但儘管最簡單的版本比霍夫曼編碼更慢且更複雜，算術編碼不會顯著增加其計算或演算法複雜度。當輸入機率不是精確已知或在流內顯著變化時，這種靈活性特別有用。然而，霍夫曼編碼通常更快，並且算術編碼在歷史上是專利問題的一些主題。因此，許多技術歷來避免使用有利於霍夫曼和其他字首編碼技術的算術編碼。截至2010年中期，隨著早期專利的到期，這種替代霍夫曼編碼的最常用技術已經進入公有領域。對於具有均勻機率分佈的一組符號，以及作為2的冪之成員，霍夫曼編碼等同於簡單的二進位制編碼，例如 ASCII 編碼。這反映瞭如此的事實：無論壓縮方法是什麼，這種輸入都不可能進行壓縮，或只是說對資料無所作為，比起壓縮才是最佳選擇。在任何情況下，霍夫曼編碼在所有方法中是最佳的方式，其中每個輸入符號是具有二元機率的已知獨立且相同分佈的隨機變數。字首碼，特別是霍夫曼編碼，往往在小字母表上產生較差的效率，其中機率通常落在這些最佳點之間。當最可能符號的機率遠超過0.5時，可能發生霍夫曼編碼的最壞情況，使低效率的上限無限制。在使用霍夫曼編碼的同時，有兩種相關的方法可以解決這種特定的低效問題。將固定數量的符號組合在一起壓縮。隨著塊的大小接近無窮大，霍夫曼編碼理論上接近熵限制，即最佳壓縮。然而，阻塞任意大的符號組是不切實際的，因為霍夫曼程式碼的複雜性在要編碼的可能性的數量上是線性的，這是在塊的大小中呈指數的數字。這限制了在實踐中完成的阻塞量。廣泛使用的實際替代方案是行程編碼。該技術在熵編碼之前增加一步，特別是對重複符號進行執行次數的計數，然後對其進行編碼。對於伯努力編碼在編碼遊程長度的字首碼中是最佳的，這是透過霍夫曼編碼技術證明的事實。使用改進的霍夫曼編碼的傳真機採用類似的方法。但是，遊程編碼並不像其他壓縮技術那樣適應許多輸入型別。變化.霍夫曼編碼有衍生出許多的許多變化，其中一些使用類似霍夫曼的演算法，而其他一些演算法找到最佳字首碼。注意，在後一種情況下，該方法不需要像霍夫曼那樣，實際上甚至不需要到多項式複雜度。多元樹霍夫曼編碼.多元樹霍夫曼編碼演演算法使用字母集 {0, 1, ... , "n" − 1} ，來構建一棵 "n" 元樹。霍夫曼在他的原始論文中考慮了這種方法。這與二進位制演算法僅有的差別，就是它每次把 "n" 個最低權的符號合併，而不僅是兩個最低權的符號。倘若 n ≥ 2, 則並非所有源字集都可以正確地形成用於霍夫曼編碼的多元樹。在這些情況下，必須新增額外的零機率佔位符。這是因為該樹必須為滿的 "n" 叉樹，所以每次合併會令符號數恰好減少 ("n" -1), 故這樣的 "n" 叉樹存在當且僅當源字的數量模 ("n" -1) 餘 1. 對於二進位制編碼，任何大小的集合都可以形成這樣的二叉樹，因為 "n" -1 = 1.自適應霍夫曼編碼.自適應霍夫曼編碼的變化，涉及基於源符號序列中的最近實際頻率動態地計算機率，以及改變編碼樹結構以匹配更新的機率估計。它在實踐中很少使用，因為更新樹的成本使其比最佳化的自適應算術編碼慢，後者更靈活並且具有更好的壓縮。霍夫曼模板演演算法.在霍夫曼編碼的實現中，通常會使用權重表示數值機率，但是上面給出的演算法不需要這樣;它只需要權重形成一個完全有序的可交換麼半群，這意味著一種訂購權重和新增權重的方法。霍夫曼模板演算法使人們能夠使用任何型別的權重，這個問題首先應用於電路設計。長度限制霍夫曼編碼/最小變異霍夫曼編碼.長度限制霍夫曼編碼.長度受限的霍夫曼編碼是一種變體，其目標仍然是實現最小加權路徑長度，但是存在另外的限制，即每個碼字的長度必須小於給定常數。包合併演算法透過一種與霍夫曼演演算法非常相似的簡單貪婪方法解決了這個問題。不相等成本霍夫曼編碼.在標準的霍夫曼編碼問題中，假設集合中構成碼字的每個符號具有相同的傳輸成本：長度為"N"位的碼字總是具有"N"的成本，無論多少這些數字是0，有多少是1，等等。在這個假設下工作時，最小化訊息的總成本和最小化數字總數是相同的。具有不等字母成本的霍夫曼編碼是沒有這種假設的概括：由於傳輸介質的特性，編碼字母表的字母可能具有不均勻的長度。一個例子是摩爾斯電碼的編碼字母表，其中'破折號'比'點'需要更長的傳送時間，因此傳輸時間中破折號的成本更高。目標仍然是最小化加權平均碼字長度，但僅僅最小化訊息使用的符號數量已經不夠了。沒有演算法以與傳統霍夫曼編碼相同的方式或相同的效率來解決這個問題，儘管它已經由卡普的整數成本的情況進行了改進。最佳字母二元樹.在標準霍夫曼編碼問題中，假設任何碼字可以對應於任何輸入符號。在字母表中，輸入和輸出的字母順序必須相同。規範霍夫曼編碼.如果對應於按字母順序排列的輸入的權重是按數字順序排列的，則霍夫曼程式碼具有與最佳字母程式碼相同的長度，這可以從計算這些長度中找到，從而不需要使用胡 - 塔克有序輸入產生的程式碼有時被稱為規範霍夫曼程式碼，並且由於易於編碼/解碼，通常是實踐中使用的程式碼。用於找到該程式碼的技術有時被稱為霍夫曼 - 夏農 - 法諾編碼，因為它像霍夫曼編碼一樣是最優的，但是在重量機率上是字母的，例如夏農 - 法諾編碼。資料長度.設符號集合formula_1，formula_14為formula_15發生的機率，formula_16為formula_17編碼的長度formula_18ex:formula_19formula_20formula_21formula_22第三與第四個範例，同樣是五種組合，機率分佈越集中，則亂度越少formula_23Shannon編碼定理： formula_24 ≤ formula_25 ≤ formula_24 formula_27 ，若使用formula_28進位的編碼霍夫曼碼的平均編碼長度：設formula_29，formula_30為資料長度formula_30formula_32 ≤ formula_33 ≤ formula_30formula_32 formula_36範例.(a)direct:假設結果為：白色為00、咖啡色01，藍色10和紅色11個bits則結果為:100*2 = 200bits(b)huffman code: (must be satisfy the following conditions，if not change the node)(1) 所有碼皆在Coding Tree的端點，再下去沒有分枝(滿足一致解碼跟瞬間解碼)(2) 機率越大，code length越短；機率越小，code length越長(3) 假設formula_37是第L層的node，formula_38是第L+1層的node則formula_39必須滿足假設結果為：白色佔0、咖啡色10，藍色110和紅色111個bits則結果為:60*1+20*2+20*3=160bits相互比較兩個結果huffman code 整整少了40bits的儲存空間。示範程式.// 以下為C++程式碼，在G++下編譯透過// 僅用於示範如何根據權值建構霍夫曼樹，// 沒有經過效能上的最佳化及加上完善的異常處理。using namespace std;const int size = 10;struct node { // 霍夫曼樹節點結構unsigned key; // 儲存權值node *lchild; // 左孩子指標node *rchild; // 右孩子指標deque forest;deque code; // 此處也可使用bitsetnode *ptr;int frequency[size] = {0};void printCode(deque ptr); // 用於輸出霍夫曼編碼bool compare( node *a, node *b) {return a-&gt;key key;int main(int argc, char *argv[]) {for (int i = 0; i code);return 0;