用已知概率分佈壓縮符號的最佳熵編碼方案是什麼？

Question

我正在尋找編碼user_ids在長長的通話記錄列表。佔用最多空間的這些記錄的部分是呼叫者和接收者的符號。我將創建一個映射，將最活躍的調用者分配更短的符號---這將有助於保持文件的整體大小（並因此減少I/O時間）。

我事先知道多少次的每個符號將被用於---換句話說，我所知道的相對概率分佈。此外，生成的代碼是「前綴無關」的，例如霍夫曼代碼並不重要。那麼什麼是最好的編碼方案，即能夠提供最大壓縮率和快速實現的編碼方案？

的答案應該不僅指向一個壓縮方案，它應該也指向編碼方案的實現。

Answer 1

對於通用無損編碼與已知的概率分佈，除了哈夫曼編碼，其他的「教科書」的答案是arithmetic coding。

在實踐中，有多種實現方法。見these general-purpose coders。每個都有不同的屬性。沒有進一步的信息，我們不能給你一個更準確的答案。

Answer 2

@conradlee：重新「？在哪些情況下是算術編碼比哈夫曼編碼更好」就壓縮而言，幾乎總是。如果你有一個符號S，其概率爲Ps，那麼編碼它的理想位數bs是-log（Ps）/ log（2）。例如，如果Ps是1/3，則bs是〜1.585位。隨着霍夫曼您有舍向上或向下位的最接近的整數（所以壓縮比會降低）。算術編碼將使用小數位來存儲它。