書記が数学やるだけ#723 ハフマン符号の構成

情報源符号化の具体例についていくつか見ていく。

問題

説明

可逆圧縮の例をいくつかまとめておく。

ハフマン符号は1952年にデビッド・ハフマンによって開発された。構成法を簡単にいうと，出現確率の小さいものから順に符号を増やしていくことで割り当てを行う。

解答

シャノン符号化は接頭符号の最初のもので、1948年のシャノンの記事『通信の数学的理論』でシャノンの情報源符号化定理の証明のために用いられた。これを元として，数多くの符号化が開発された。

シャノン符号は簡便だが，コンパクト符号ではない。

ハフマン符号は共通テストの情報関係基礎2023でも題材にされた（暗号化との複合問題）。

ハフマン符号の優れている点として，コンパクト符号（情報源に対し最短の符号）であることが挙げられる。

これを示すには数学的帰納法により，最小単位から木を組み立ていくことで示していく。

本記事のもくじはこちら：