Huffman壓縮的最後一個字節

我在想什麼是處理Huffman Copression中最後一個字節的最佳方法。我在C++中有一些很好的代碼，可以非常好地壓縮文本文件，但是現在我必須向我的編碼文件寫入一些編碼字符（呃，它等於輸入文件大小），因爲不知道如何處理最後一個字節更好。Huffman壓縮的最後一個字節

例如，要壓縮的最後一個字符是'a'，該代碼是011，我剛剛開始寫入新的字節，因此最後一個字節將如下所示： 011 +某些5位垃圾，我正在製作例如最後它們爲零。而當我編碼這個編碼文件時，可能會發生代碼00000（或用較少的零）是某些字符的代碼，所以我將在我的編碼文件的末尾有一些垃圾字符。

正如我在第一段中寫的，我通過在編碼文件中保存輸入文件的字符數來避免這種情況，並且在編碼時，我正在讀取編碼文件以達到該編號（而不是EndOfFile，不要得到這些例子5個零）。這並不是真的有效，編碼文件的大小增加了很長的數字。

如何以更好的方式處理這個問題？

PS。對不起，我不完美的英語，我希望它有可能明白:-)

來源

2013-02-02 Horuss

你的方法（寫入文件的編碼字節數）是一個完全合理的方法。如果你想嘗試不同的途徑，你可以考慮發明一個新的「僞EOF」字符，標記輸入的結尾（我將它表示爲＆方形）。無論何時您想壓縮字符串s，您都會壓縮字符串s＆square ;.這意味着當你建立你的編碼樹時，你會包含一個＆字符，以便您擁有＆square;的唯一編碼。然後，當你寫出文件的字符串時，你會寫出正常的字符串的位字符，然後寫出＆方式的位模式。如果有剩餘位，則可以任意設置它們。

這種方法的優點是，當你解碼文件時，如果在任何時候你找到＆square;字符，你可以立即停止解碼位，因爲你知道你已經擊中了文件的末尾。這不需要您存儲任何地方寫出的字節數 - 編碼隱式標記其自己的端點。

這種設置的缺點是它可能會增加某些字符使用的位模式的長度，因爲您需要將位模式分配給＆square;除了所有其他角色。

我教一門入門性的編程課程，我們使用霍夫曼編碼作爲我們的任務之一。我們讓學生使用上述方法，因爲它比寫出文件內容之前的位數或字節數容易一些。有關更多詳細信息，請參閱課程中的this handout或these lecture slides。

希望這會有所幫助！

來源

2013-02-02 23:39:41 templatetypedef

確實沒有缺點，因爲你可以證明這不會比編碼長度需要更多的位。 –

@ MarkAdler-你有參考嗎？我經常想到這一點，但我從未見過正式的證據。 – templatetypedef

我不記得我在哪裏看到那個。我會尋找它。 –

我知道這是一個古老的問題，但仍有一個替代方案，所以它可能有助於某人。

當你寫你的壓縮文件輸出時，你可能有一些整數跟蹤你在當前字節中的位置（用於位移）。

char c, p; 
p = '\0'; 
int curr = 7; 
while (infile.get(c)) 
{ 
    std::string trav = GetTraversal(c); 
    for (int i = 0; i < trav.size(); i++) 
    { 
     if (trav[i] == '1') 
      p += (1 << curr); 
     if (--curr < 0) 
     { 
      outfile.put(p); 
      p = '\0'; 
      curr = 7; 
     } 
    } 
} 
if (curr < 7) 
    outfile.put(p);

在該塊的末端，(curr+1)%8等於垃圾比特的最後一個數據字節的數目。然後您可以將它作爲一個額外的字節存儲在最後，並且在解壓縮時記住它。

來源

2014-12-16 20:38:17

Huffman壓縮的最後一個字節

回答

相關問題