ハフマン符号化 とは？

よく出る文字には短いビット列を、めったに出ない文字には長いビット列を割り当てるんだ。日本語で「は」をいちいち「波乗り」って書かなくていいのと同じで、よく使うものは短く書いた方が全体が短くなるよね。

ハフマン木という二分木を作るんだ。出現頻度の低い文字から順にペアにして木を組み上げる。するとよく出る文字は木の上の方、めったに出ない文字は下の方に配置されて、自然と最適な符号長になるよ。

いい質問だね！ハフマン符号は「接頭符号」という性質を持っていて、ある符号が別の符号の先頭部分になることがないんだ。だから区切り記号がなくても一意にデコードできるよ。

ZIP、gzip、JPEG、PNG、MP3、MPEG……ほぼ全ての圧縮フォーマットの中で使われているよ。ちなみにハフマンが大学院生のときに課題として発明したという逸話は有名で、教授が解けなかった問題を学生が解いちゃったんだ。