エントロピー符号

エントロピー符号（エントロピーふごう）とは、情報源アルファベットのシンボルに対し符号語を割り当てるコンパクト符号の概念の一つで、シンボル毎の出現確率に基づき異なる長さの符号語長を用いることで、情報源を効率的に符号化することを目的としたもの。具体的な例としてハフマン符号や算術符号などがあり、データ圧縮に広く用いられている。

符号アルファベットの要素数を${\displaystyle n}$、任意のシンボル${\displaystyle s}$の出現確率を${\displaystyle p_{s}}$とすると、${\displaystyle -\log _{n}p_{s}}$の長さの符号語を割り当てた時に最短の符号が得られることが知られている。当然、任意の情報源に対してこれらの最適な符号語長は整数にはならない。ハフマン符号では、ハフマン木を用いて各符号語長が整数になるように近似しているため、簡便な手法ではあるが最短の符号は得られない。算術符号は半開区間の分割を繰り返すことで、この問題を克服している。

エントロピー符号を復号するには、情報源アルファベットの各出現確率を事前に通知する必要がある。これに対し、復号が完了したデータから順次出現確率を計算する手法も存在し、適応(Adaptive)あるいは動的(Dynamic)と呼ばれる。これと区別する為に静的(Static)という呼称もある。

関連項目

• エントロピー
• シャノンの情報理論