霍夫曼壓縮是如何工作的

Question

當我試圖通過霍夫曼編碼對以下流進行編碼時，我遇到了一些問題。 如果編碼系統是

A：0 B：10 C：110 d：111

則序列ABBADC將010100111110. 如何當我收到它我解碼此比特流？ 編碼系統是否必要？ 如果是這樣，我該如何發送此表？ 如果不是，我應該如何解碼它們？

Answer 1

你必須建立一個樹

Start 
/0 \1 
| /0 \1 
A | /\ 
    B | | 
     C D 

而且隨着它的每一步以下的二進制數字移動。每次找到葉時間 - 返回根

你應該把這個表無論是在你的文件的特殊頭部分或完全分開

Answer 2

傳統的樹狀數據結構是用來存儲數據的霍夫曼。所以當你處理A，B，C，D時，你繼續構建一棵二叉樹。編碼的值即A，B，C，D被存儲在葉中。 當您收到一個比特流時，您只需遍歷樹就可以解碼代碼。

就你而言，如果你只有這4個輸入，那麼我會建議使用散列圖而不是樹，因爲它會讓你的查找更容易。

Answer 3

您不需要發送表，只是位長度。即，1,2,3,3。給定位長度，可以在編碼和解碼兩端以相同方式構建規範前綴代碼。有關規範代碼的更多信息，請參見this answer。

有很多方法可以解碼前綴代碼。你可以一點一點地走，就好像你正在遍歷一棵樹，最終結束於一個符號的葉子。然後從樹的根部開始回到下一位。

或者對於規定較短長度的長度小於長度較長的規範代碼，將位收集爲整數並與每個長度值的表進行比較。一旦長度建立，整數索引一個符號表。這是示例代碼puff.c所做的。

最快的方法之一是有一個表，其長度包含最長的代碼，其中每個表項是符號和位數。具有較少位的代碼具有多個表項。在這種情況下：

000: A 1 
001: A 1 
010: A 1 
011: A 1 
100: B 2 
101: B 2 
110: C 3 
111: D 3 

然後，您讀取三位數據，查找它，在表格中發射符號，並消耗指示的位數。然後根據需要獲取更多比特以回到三比特並重復。如果你到達輸入的末尾，只需填寫零位但記下多少。如果解碼代碼使用填充位，則標記錯誤。

這就是zlib's inflate代碼的功能，儘管它更復雜一點，因爲builds a two-level table因此不會花費太多時間來構建長表。