預測Huffman壓縮比率而不構建樹

Question

我有一個二進制文件，我知道其中每個符號的出現次數。我需要預測壓縮文件的長度，如果我使用霍夫曼算法對它進行壓縮。我只對假設的輸出長度感興趣，而不是對單個符號的代碼感興趣，因此構建霍夫曼樹似乎是多餘的。
作爲一個例子，我需要得到像
「38位的二進制字符串，其中包含4個a，5個b和10個c可以壓縮到28位」，除了文件和字母大小都大得多。

基本問題是：它可以在沒有構建樹的情況下完成嗎？

望着貪心算法：http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
好像樹可以的n * log（n）時間，其中n是在文件中不同符號的數量來構建。這漸近地不壞，但需要樹節點的內存分配，並做了很多工作，這在我的情況下是浪費。

Answer 1

壓縮文件中每個符號的平均比特數的下限不過是輸入中所有符號x的熵H = -sum(p(x)*log(p(x)))。 P(x) = freq(x)/(filesize)。使用這個compressed length(lower bound) = filesize*H。這是壓縮文件大小的下限。但不幸的是，最佳熵在大多數情況下是不可實現的，因爲比特是不完整的，所以在實際情況下需要構造霍夫曼樹來獲得正確的壓縮大小。但是，可以使用最佳壓縮大小來獲得壓縮量的上限，並決定是否使用huffman。

Answer 2

可以通過上部 ħ結合在霍夫曼編碼每個碼元的平均比特計數（P1，P2，...，PN）+ 1其中ħ是熵，每個PI是符號的概率i發生在輸入中。如果您將此值乘以輸入大小N，它會給出編碼輸出的近似長度。

Answer 3

您可以輕鬆修改算法以在數組中構建二叉樹。根節點位於索引0，其左側節點位於索引1，右側節點位於索引2處。通常，節點的子節點位於(index*2) + 1和(index * 2) + 2。當然，這仍然需要內存分配，但是如果知道有多少個符號，則可以計算樹中將有多少個節點。所以這是一個單獨的數組分配。

我不明白所做的工作真的浪費在哪裏。你必須跟蹤組合邏輯以某種方式，並且如圖所示在樹中執行它非常簡單。我知道你只是在尋找最終答案 - 每個符號的長度 - 但是如果你不做這些工作，你就無法得到答案。