如何高效地解壓哈夫曼編碼文件

Question

我發現了很多問題，但一些解釋很難理解，我不能完全理解如何有效解壓文件的概念。 我發現這些相關的問題： Huffman code with lookup table How to decode huffman code quickly?

但我不明白的解釋。我知道如何定期編碼和解碼huffman樹。現在在我的壓縮程序，我可以寫任何的以下信息文件 符號 霍夫曼碼（無符號長） 霍夫曼碼長

我打算做的就是一個文本文件，它分成小的文本文件並分別壓縮每個文件，然後通過將所有小型壓縮文件及其各自的查找表（不知道該如何執行此部分）發送到Nvidia GPU來嘗試使用某種查找方式並行解壓縮文件來解壓該文件表。

我有3個問題： 我應該在頭文件中寫入什麼信息來構造查找表？ 如何從文件重新創建此表？ 如何快速解碼huffman編碼文件？

Answer 1

不要打擾自己寫，除非這是一個教學練習。使用zlib,lz4或任何其他幾個免費壓縮/解壓縮庫，這些庫比任何你能做的都要好得多。

你只是在談論霍夫曼編碼，表明你只會得到一小部分可用的壓縮。提到的庫中的大部分壓縮來自匹配字符串。查看「LZ77」。至於高效的霍夫曼解碼，你可以看看zlib的膨脹是如何實現的。它爲代碼的最重要的九位創建一個查找表。表中的每個條目都有一個符號和該代碼的位數（小於或等於9），或者如果提供的9位是較長代碼的前綴，則該條目具有指向另一個表的指針以解析代碼的其餘部分以及該次表所需的位數。 （有幾個這樣的次表）。如果代碼長度小於9，則同一符號有多個條目。實際上，對於一個n位代碼來說，多個條目是多個條目。

所以要解碼你從輸入中得到9位並從表中獲取條目。如果它是一個符號，則從流中刪除爲該代碼指示的位數併發出符號。如果它是一個指向輔助表的指針，則從流中刪除9位，獲取表中指示的位數，然後在那裏查找它。現在，您一定會得到一個要發射的符號，以及要從流中移除的剩餘位數。