ハフマン符号とは

ハフマン符号とはデータの圧縮方式です。コンピュータは0と1しか利用できないという特性を持っています。その中で数万種類の文字を扱っています。これらの文字は最終的に当然0と1に変換されCPUで処理されますが何も考えずにただ0と1を割り当てればデータに無駄ができてしまいます。

無駄を省く仕組み

例えばよく使う文字「A」に0101011001100110を割り当てたとしましょう。そしてたまーにしか使わない文字「璽」に0を割り当てたとします。Aを打つたびに16ビットのデータを使います。璽は1ビットです。HDDもCPUリソース、ネットワーク回線も物理的に上限がありますよね？ということはこれらのデータはできれば効率よく使用したいものです。という考え方で

よく使う「A」のような文字にはなるべくシンプルなコードを
「璽」のようなまれに使う文字には長いコードを

割り当てることでデータの圧縮を実現しています。

ハフマン符号は先頭から順番に読み込まれる

ハフマン符号は先頭から順番に読み込まれます。これは問題を解く際にも使う重要な概念なので覚えておきましょう。

先頭部分が被らない｜プレフィックスフリー

例えば2つの文字があったとして「A」に01「B」に011と割り当てて先頭から読み込んでいくと「B」の01部分でAと判断されてしまいます。これは前述の先頭から読み込んでいくという特性が働くからなんですね。

では「B」に11と割り当てたらどうでしょうか？11であれば先頭から呼んでいってもBと判断できます。
ABは0111
BAは1101
ABAは011101
BABは110111
大丈夫そうですね。