ハフマン符号とは？はふまんふごう
ハフマン符号とは、記号ごとの出現確率が分かっているとき、平均符号長が最小になる可変長符号を機械的に構成するアルゴリズム。確率の小さい二つを束ねる操作を繰り返して二分木を作るため、どの符号語も他の符号語の先頭部分にならず、区切り記号を挟まなくても受信側が一意に復号できる符号が得られる。
最終更新：2026-10-06
この語が出る過去問を解く →背景
すべての文字に同じビット幅を割り当てていた時代は、頻出する文字も滅多に出ない文字も同じ容量を食い、回線と記憶媒体を無駄に使っていた。長さを可変にすれば縮むが、境界が分からなくなって復号できない。この「縮めたいが区切れなくなる」対立を、接頭辞にならない符号語の集合を確率だけから導くことで調停したのがハフマンの手続きである。理論値であるエントロピーにどこまで近づけるかという評価軸を持ち込んだ点で、情報量の計算とセットで問われる。
具体例
デビッド・ハフマンが1952年にMITで考案し、いまもZIPやgzipのDEFLATE、JPEGのエントロピー符号化段で使われている。A=0.5、B=0.25、C=D=0.125なら符号は0・10・110・111となり、平均符号長は0.5×1+0.25×2+0.125×3×2＝1.75ビット。固定長の2ビットより12.5%短い。
試験での引っ掛け
圧縮率は最短の符号語の長さではなく、平均符号長＝Σ（出現確率×符号長）で評価する。木の形は結合の順序によって複数あり得るが、そのどれを選んでも平均符号長は同じ値になる。逆に全記号の確率が等しい場合は縮まず、固定長符号と同じ長さになる。
関連用語
出た過去問
出典：平成30年度 秋期 応用情報技術者試験 午前 問5（IPA）解説で登場
符号化方式に関する記述のうち，ハフマン方式はどれか。
正解：発生確率が分かっている記号群を符号化したとき，1記号当たりの平均符号長が最小になるように割り当てる。
要点：ハフマン符号は出現確率に応じ平均符号長を最小化する可変長符号。
ハフマン方式は、各記号の出現確率が既知のときに、出現しやすい記号ほど短い符号を割り当てることで、1記号当たりの平均符号長を最小にする可変長符号化である。符号木を出現確率の小さいものから併合して構成するため、語頭符号（前置符号）となり復号も一意に行える。ZIPやJPEGなど多くの圧縮方式の内部で使われている。
出典：平成30年度 春期 応用情報技術者試験 午前 問2（IPA）解説で登場
表は、文字A～Eを符号化したときのビット表記と、それぞれの文字の出現確率を表したものである。1文字当たりの平均ビット数は幾らか。
正解：1.8
要点：平均符号長は符号長と出現確率の積の総和で求める
平均ビット数は、各文字の符号長にその出現確率を掛けて合計した期待値として求める。0.5×1＋0.3×2＋0.1×3＋0.05×4＋0.05×4＝0.5＋0.6＋0.3＋0.2＋0.2＝1.8ビットとなる。出現頻度の高い文字ほど短い符号を割り当てるハフマン符号の考え方で、単純な3ビット固定長より効率が良いことが分かる。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (2) 符号理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。