ハフマン符号化ビジュアライザー

Huffman encoding optimizes data compression by dynamically constructing a binary tree based on the statistical frequency of input symbols. It assigns mathematically shorter bit sequences to highly probable characters, achieving the theoretical limit of Shannon entropy. The strict requirement of prefix-free codes guarantees unambiguous algorithmic decoding. This deterministic reallocation of binary weight mathematically minimizes the total file size without any loss of data.

木は下から上へ組み立てられます。まず各文字を出現頻度順に並べ、次に最も頻度の低い二つの要素を小さな部分木にまとめ、一つの束として扱う操作を繰り返します。木が一つになるまで続け、最後に頂点から下りながら符号を読み取ります。左が 0、右が 1 です。常に最小の二つを結ぶこの「貪欲な」やり方は近視眼的に見えますが、証明上もっとも短い符号を生み出します。

デイヴィッド・ハフマンは1951年、MITの大学院生だったときにこれを考案しました。ロバート・ファノ教授が、期末試験か「最も効率的な符号を見つける」レポートかを学生に選ばせたのです。ファノとクロード・シャノンはすでに挑戦し、木を上から下へ構築していました。ハフマンは諦めかけましたが、下から上へ――最も稀な記号から併合する――のが最適だと気づき、自分の教授の方法を上回りました。