適應性霍夫曼編碼 | 2021全台活動資訊網

适应性哈夫曼编码（英語：AdaptiveHuffmancoding），又称动态哈夫曼编码（Dynamic...在霍夫曼編碼中，有個缺點是除了壓縮後的資料外，它還得傳送機率表給解碼端，否則解碼端無法正確地做解碼的工作。如果想要壓縮好一點，必須有更多 ...

適應性霍夫曼編碼（英語：Adaptive Huffman coding），又稱動態霍夫曼編碼（Dynamic Huffman coding），是基於霍夫曼編碼的適自適應編碼技術。它允許在符號正在傳輸時構建代碼，允許一次編碼並適應數據中變化的條件，即隨著數據流的到達，動態地收集和更新符號的概率（頻率）。一遍掃描的好處是使得源程序可以實時編碼，但由於單個丟失會損壞整個代碼，因此它對傳輸錯誤更加敏感。

在霍夫曼編碼中，有個缺點是除了壓縮後的資料外，它還得傳送機率表給解碼端，否則解碼端無法正確地做解碼的工作。如果想要壓縮好一點，必須有更多的統計資料，但同時必須要送出更多的統計資料到解壓縮端。而適應性編碼可以利用已經讀過的資料機動的調整霍夫曼樹。適應性霍夫曼編碼中，演算法FGK的基本原則是根據兄弟性質（Sibling Property），由Gallager定義。

一顆霍夫曼樹只是一棵在每個節點，包括樹葉與內節點，加上加權值的二元樹，除了樹根外，每一個節點都有一個兄弟節點與其共有一個父親節點。如果每一個節點可以按照加權值從小排列到大且每個節點又再自己的兄弟相鄰，稱為兄弟性質。修改、或更新一棵霍夫曼樹包括兩個步驟。第一個步驟是頻率次數的增加，先找到該葉子，把頻率加一，在往上找他的父親節點，也跟著加一，直到樹根皆照著此步驟。第二個步驟是如果增加加權值的動作使得兄弟性質不再滿足時，必須做調整的動作，藉由交換葉子改變頻率增加的順序，同時，交換位置後的父親節點加權值也要跟著更新，以此原則使之再度成為霍夫曼樹。

在演算法FGK中，傳輸端與接收端同時動態的去改變霍夫曼樹，最初，解碼樹由單一葉子組成，稱之0端。0端是用來代表未出現過的訊息，當每一個訊息傳遞後，增加此訊息的出現頻率並調整霍夫曼樹保持兄弟性質。當有t個訊息傳遞後，之中有k個不同的訊息，代表此霍夫曼樹有k+1的葉子，k個葉子有訊息，1個代表0端。當下次傳遞新訊息時，此訊息夾帶未出現過的資訊，0端的葉子此時分成2片葉子，1片給新訊息，另一片為新的0端。

考慮適應性霍夫曼編碼的效能問題，更有效能的方法是確認編碼端不會浪費空間在不存在的符號上，一般的霍夫曼編碼容易做到是因為在建立霍夫曼樹之前，會統計所有的資料，就能先算出各訊息...