100 万個のシンボルとその予想頻度の表があります。
各シンボルに一意の (およびプレフィックスが一意の) 可変長ビット文字列を割り当て、これらを連結してシーケンスを表すことにより、これらのシンボルのシーケンスを圧縮したいと思います。
エンコードされたシーケンスの予想されるビット長が最小になるように、これらのビット文字列を割り当てたいと思います。
たとえば、シンボルと予想される頻度が次の場合:
foo 0.5
bar 0.25
baz 0.25
最良のエンコーディングの 1 つよりも次のようになります。
foo 0
bar 10
baz 11
したがって、「foobarbazfoo」は 010110 に変換されます。
どのアルゴリズムを使用して、期待される頻度の表を最適なエンコード方式に変換できますか?