ハフマン符号

ハフマン符号は情報圧縮における可逆符号（正確に復号できる符号）です。 画像や音声の情報圧縮では、まず非可逆圧縮を行い、残った規則的な（人間が理解可能な）対象に対して、可逆符号による圧縮を実施します（情報圧縮を参照）。 無記憶情報源のいかなる復号可能符号の平均符号長も、その情報源のエントロピー以下にすることはできないことは符号とエントロピーで説明しました。 では、復号可能な符号のなかで、 もっとも平均符号長の短い符号（もっともエントロピーに近い符号）を どのようにして設計すればよいでしょうか？ その符号は、瞬時復号可能な符号の中から見つかり、ハフマン (David.A.Huffman, 1925-1999) がその設計法を示しました。 どの符号語も他の符号語の接頭語になっていない符号は瞬時的に復号可能です。 このような符号は、視覚的に分かりやすい構造をもっています。 下図のように、２本の枝分