用文本編碼哈夫曼表

我有一個實現霍夫曼編碼來編碼文本的代碼。用文本編碼哈夫曼表

鑑於以下文本

abbccc

我的程序產生如下表

a -> 00 
b -> 01 
c -> 1

所以編碼文本（位陣列）是

000101111

問題是：我需要將表格與文本一起編碼，我不知道這是什麼建議的方法。

我至今認爲：

第一個字節是在表
鍵值對繼N * N的數目2個字節的鍵值對自己（關鍵一個字節爲值，一個字節）
其餘位編碼的文本本身

你可以建議我多些靈活而廉價的（低內存佔用）這個方法？

來源

2017-06-03 Gabriel

我很確定DEFLATE算法使用霍夫曼編碼..你可以看看他們是如何做到的。警告文件有點密集且難以理解。我還沒有理解它。從我幾年前回想起來，如果按照特定的步驟構建huffman樹，然後按照某種排序順序存儲KVP，則存在唯一的表示形式，這使得存儲表非常緊湊。 https://www.ietf.org/rfc/rfc1951.txt – ithenoob

如果您希望以最小的可能尺寸存儲表格（您並不真正說出「便宜」的含義），那麼請查閱經典的霍夫曼編碼。對於初學者，https://en.wikipedia.org/wiki/Canonical_Huffman_code。我_think_這是@ithenoob正在討論的內容？ – Gene

@Gene：我特別提到了DEFLATE管理它的字典的方式，我相信它也以某種神祕的方式被壓縮。然而，你鏈接到的維基百科頁面似乎更有希望，因爲它更具可讀性，並明確指出將討論緊湊的霍夫曼表示。 – ithenoob

Deflate RFC1951將Huffman表存儲在壓縮數據的前面。參見第3.2.7節。你不需要存儲代碼（在你的情況下爲00,0,1,1），但它們的長度（即2,2,1）。第3.2.2節描述了在解壓縮時如何將這些長度轉換回代碼。該表由所有符號的長度序列描述，在你的小例子中它將是類似於0,0,0，...，2,2,1，... 0的東西。零表明這些符號不出現在文件中，除了長度爲2,2,1的a，b，c。爲了使這張表的長度緊湊，你可以做運行長度編碼。在Deflate（第3.2.7節）中，長度符號18（n）將n次長度的序列編碼爲0。下一個問題是如何編碼長度符號'18'？您可以使用5位代碼來表示長度符號0到18，以使其更簡單。或者你也可以用Huffman對它們進行編碼，例如用Deflate的0-7位代碼。

來源

2017-06-03 12:31:12

用文本編碼哈夫曼表

回答

相關問題