我正在修改我的編程技巧並實現了霍夫曼算法。目前，我只考慮沒有特殊字符的[a-z]。 a-z的概率值已從wikipedia中使用。測量霍夫曼算法的壓縮
當我運行它時，我對隨機段落進行了大約2倍的壓縮。 但是對於這個計算，我假設每個原始字母需要8位（ASCII）。
但是如果我考慮一下，代表26個項目，我只需要5位。如果我計算基於這個事實，然後壓縮係數下降到近11
所以我的問題是，如何在壓縮因素在現實世界中的應用程序確定的？
第二問題 - 如果我寫編碼器/譯碼器，它使用5個比特用於表示A-Z（說= 0，B = 1，等等） - 這是一個也被認爲是有效的 「壓縮」 算法？
你有本質上是正確的答案，這是你不能指望大量壓縮的，如果所有你正在使用的是英語語言的字母頻率。
來計算信頻率的知識所產生的收益，正確的方法是考慮等於概率與英文字母的熵的26個符號字母的熵。
（祝計算器允許TeX的方程一樣math.stackexchange.com一樣。然後，我可以在這裏寫像樣的方程。哦。）
關鍵公式爲-p日誌（p），其中p爲該符號的概率和日誌以2爲單位得到答案。您爲每個符號計算此值，然後對所有符號進行求和。
然後，在一個理想的算術編碼方案，等概率集合26的符號將被在每個碼元4.70位編碼。對於英文發行（使用Wikipedia article的概率），我們得到每個符號4.18位。減少只有約11％。
這就是所有的頻率偏差本身可以買到你。 （它在拼字遊戲分數中給你帶來了很多，但我離題了）
我們也可以在霍夫曼編碼的近似空間中看到同樣的東西，其中每個代碼都是整數位。在這種情況下，您將而不是假設每個字母五位（浪費了六個代碼）。將霍夫曼編碼應用於26個相同概率的符號給出六個長度爲四位的代碼和長度爲五位的20個代碼。這導致平均每個字母4.77位。使用英文字母頻率的霍夫曼編碼給出每個字母平均4.21位。減少12％，這與熵計算大致相同。
真正的壓縮機有很多方法比這更好。首先，他們用文件中的實際內容編碼，使用那裏的內容的頻率而不是英語的內容。這使得它與語言無關，針對實際內容進行優化，甚至不編碼不存在的符號。其次，你可以把輸入分解成幾部分，併爲每個輸入一個新的代碼。如果這些塊足夠大，那麼傳輸新代碼的開銷很小，並且增益通常較大以在較小的塊上優化。第三，你可以尋找更高階的效果。您可以考慮前面的字母，並查看下一封給其前任的字母的概率，而不是單個字母的發生頻率。現在你有26^2個概率（僅用於字母）來跟蹤。這些也可以爲實際數據動態生成，但現在需要更多數據才能獲得增益，更多內存和更多時間。您可以使用三階，四階等來獲得更高的壓縮性能，但需要耗費內存和時間。
還有其他一些方案可以通過例如進行遊程編碼，尋找匹配的字符串，應用塊轉換，標記化XML，增量編碼音頻或圖像等來預處理數據，以便進一步暴露熵編碼器的冗餘，然後利用。我提到了算術編碼，它可以用來代替霍夫曼，以小於1位的方式編碼非常可能的符號，並且所有符號都可以達到分數位精度，從而在熵步驟中獲得更好的性能。回到你的壓縮問題，你可以從任何你喜歡的起點開始，例如，每個字母一個八位字節，對你的輸入做出斷言，例如所有小寫字母（接受如果斷言是錯誤的，則該方案失敗），然後評估壓縮效率。只要在比較兩種不同的壓縮方案時使用所有相同的假設。您必須小心，依賴於數據的任何內容都必須被視爲壓縮數據的一部分。例如。從數據塊派生的定製霍夫曼碼必須與該數據塊一起發送。
它不是爲26字符5個比特它的日誌（26）/日誌（2）= 4,7位。這是最大熵，但你需要知道具體的熵。德語爲4,0629。當你知道你可以用公式R = HMAX - H.看看這裏：http://de.wikipedia.org/wiki/Entropie_(Informationstheorie） http://en.wikipedia.org/wiki/Information_theory#Entropy
如果你跑，你會得到相同的結果相同的文本的無限制哈夫曼編碼壓縮，所以我覺得有理由說你通過對相同文本的ASCII編碼進行2倍壓縮。我更傾向於說你的程序正在獲得預期的壓縮，但是目前有一個限制，即它不能處理任意輸入，以及其他更簡單的壓縮方案，以便通過ASCII進行壓縮，如果該限制已到位。
爲什麼不擴展你的算法來處理任意字節值？這樣做比較容易做出真正的比較。
這是〜4.7;如果您使用每個符號的整數位數編碼等於5來編碼。 – jacobm
jacobm：嗯，但也有半位等壓縮。給予正確的信息不是更好嗎？霍夫曼算法只是一種方法。 – Bytemain
在OP的問題中，他清楚地談到只使用類似ascii的編碼方案，它將每個小寫字母映射到固定數量的位，爲此他是正確的，你需要5個。確實，你可以用因爲每個符號有6個浪費的狀態，但我不明白這與他所問的問題有什麼關係。 – jacobm