如何解碼來自霍夫曼編碼位流的消息？

Question

如何解碼來自Huffman編碼位流的消息？ 我不清楚霍夫曼算法的想法。

據我瞭解，假設我收到一條短信「我的名字是XYZ」。

然後編碼過程如下： 1.計算字符的頻率。 2.按值排序頻率。 3.構建一棵樹。 4.通過考慮左邊界爲0和右邊界爲1來遍歷樹，以獲得預期的消息字符。 5.連接代碼以查找比特流。

現在的問題是，如何從編碼比特流中找到原始消息？

我想我們需要再次構建霍夫曼樹。

但是我怎樣才能從比特流構造霍夫曼樹？

Answer 1

如果沒有原始樹，消息無法解碼。因此發送方必須在發送消息之前將其包含在消息中（如果長消息的開銷較小）或雙方同意關於樹。然後過程是相反的：你從流中讀一點點，遍歷樹。一旦你打葉子然後發射字符。

Answer 2

這裏有幾個選擇。一種是使用固定的霍夫曼樹 - 例如，如果您編碼的是正常的英文文本，則角色的相對頻率通常足夠接近常數，您可以相當合理地完成發送者和接收者事先達成的協議他們都會使用三種。

對於你描述的兩遍Huffman算法，你幾乎堅持以某種形式發送樹（連同數據）。

您也可以使用動態霍夫曼樹，您（例如）在上面的第一個選項中列出了樹，但在處理數據時，發送器和接收器都會調整樹以適應觀察結果頻率。唯一的技巧就是每個字符必須使用之前的樹進行編碼，然後進行調整，然後處理下一個字符。這樣接收端可以與發送端保持同步。