霍夫曼編碼表是如何在實踐中建立的？

Question

我的問題是具體的。我可以看到霍夫曼編碼理論很容易理解。但是，它似乎創建通常不與字節邊界對齊的代碼。減輕這個特定問題的實用方法並沒有在我所遇到的教程中討論過。

有兩個問題：

（1）一旦一個文件被編碼，文件的生成的霍夫曼碼文件的結束可能不會在字節邊界對齊。我們如何知道我們已經在壓縮文件中結束了哈夫曼編碼數據？

（2）假如文件中包含一個huffman表來幫助解壓縮，那麼在實際中如何創建這樣一個表，因爲我們再次遇到了與字節邊界的非對齊問題？符號本身可能是8位或16位。但是，霍夫曼碼可以是任意數量的比特。現在，如果我們爲每個代碼包含一個huffman代碼，我們還必須包含它的位數，因此解碼器可以使用huffman表創建二叉樹或其他數據結構來幫助解壓縮。

霍夫曼和算術編碼似乎被用於很多壓縮系統，因此這個問題不斷涌現。

我想了解這是如何在JPEG中完成的，並且將在FPGA中使用Nios II軟核處理器在C中構建編碼器，以保存來自相機的SD卡中的JPEG文件。

Answer 1

1. 附加符號被定義爲結束代碼。遇到該代碼時，您已到達流的末尾。除非有另一種類型的比特流，否則通常會丟棄最後一個字節中的任何剩餘位以進入下一個字節邊界。

2. 取決於壓縮代碼描述的重要性，有許多改變複雜性的方法。您可以閱讀RFC 1951中的deflate描述，以及RFC 7932中的brotli描述。在這兩種情況下，都不會發送代碼本身。而是發送每個符號的代碼長度，並且代碼本身是從長度和符號順序正則構建的。在收縮時，每個符號發送長度，對於未編碼的符號發送長度爲零的值。運行長度編碼的這一系列長度，然後是它本身的霍夫曼編碼。 首先發送用於解碼代碼長度的霍夫曼碼，其使用每個長度（3）的固定數量的比特發送並且再次被規範地構建。 （查找Canonical Huffman碼。）當不使用預先定義的霍夫曼碼時，JPEG有另一種編碼碼長的方法。