通話記録の長いリストにuser_idsをエンコードしようとしています。これらのレコードの中で最もスペースを占める部分は、発信者と受信者のシンボルです。最もアクティブな発信者に短い記号を割り当てるマップを作成します---これにより、ファイルの全体的なサイズ（したがってI / O時間）を抑えることができます。
各シンボルが何回使用されるかを事前に知っています---言い換えれば、相対的な確率分布を知っています。さらに、生成されるコードがハフマンコードのように「プレフィックスフリー」であることが重要ではありません。では、最高のエンコーディングスキーム、つまり、最も圧縮率が高く、迅速な実装が存在するものは何でしょうか。
答えは、圧縮スキームを指すだけでなく、そのエンコーディングスキームの実装も指す必要があります。
ハフマン符号化とは別に、既知の確率分布を持つ汎用ロスレス符号化の場合、他の「教科書」の答えは算術符号化です。
実際には、さまざまな実装があります。これらの汎用コーダーを参照してください。それぞれに異なるプロパティがあります。これ以上の情報がなければ、これ以上正確な答えを出すことはできません。
@conradlee：re 「どのような場合に算術符号化はハフマン符号化よりも優れていますか？」圧縮に関しては、ほとんどの場合。確率PsのシンボルSがある場合、それをコード化するための理想的なビット数bsは-log（Ps）/ log（2）です。たとえば、Psが1/3の場合、bsは約1.585ビットです。Huffmanを使用する場合は、最も近い整数のビットに切り上げるか切り下げる必要があります（したがって、圧縮率が低下します）。算術符号化は、小数のビット数でそれを格納します。