ハフマン符号とは
ハフマン符号（はふまんふごう）とは、データを効率よく圧縮するために開発された符号化の手法です。データの中で「よく使われる（出現頻度が高い）文字」には短いビット（短い0と1の組み合わせ）を割り当て、逆に「めったに使われない文字」には長いビットを割り当てることで、データ全体の合計サイズを最も小さく抑えることができます。この方法を使うと、文字ごとの長さを一律にするよりも大幅にデータサイズを減らすことができるため、ファイルの圧縮形式（ZIPやGZIP）や、画像の保存形式（JPEG）など、さまざまな場所でデータの通信量や保存容量を節約するために活躍しています。
具体例
「ABACABA」という、Aが多く含まれるテキストを圧縮する例を考えます。
【通常の符号化（一律2ビットずつ割り当て）】
A＝00, B＝01, C＝10 とすると、全体で 2ビット × 7文字 ＝ 14ビット必要。
【ハフマン符号（頻度に応じて長さを変える）】
一番多い A ＝ 0 （1ビット）
次に多い B ＝ 10 （2ビット）
滅多に出ない C ＝ 110 （3ビット）
と割り当てると、「ABACABA」は「01001100100」となり、合計11ビットに圧縮されます。もう少し詳しく
ハフマン符号は、1952年にデビッド・ハフマンによって提案されたアルゴリズムで、可変長符号化（文字によってビット数が異なる符号化方式）の代表例です。具体的な符号の割り当ては、「ハフマン木」と呼ばれる木構造（二分木）を下から上へと構築することで決定されます。出現確率の低い記号から順にペアを作って合流させていき、最終的に1つの根にたどり着くように木を作ります。その後、根から葉（各記号）に向かって枝をたどる際に、左に進むなら「0」、右に進むなら「1」というようにビットを割り振ることで、自動的に出現確率が高い記号には短いビット列が、低い記号には長いビット列が割り当てられる仕組みになっています。この手法により、情報理論における限界に近い非常に効率的な圧縮が可能になります。
試験でのポイント
試験では、ハフマン木を自力でたどって特定の文字の符号を求めさせる問題や、ハフマン符号を使った圧縮後の全体のビット数を計算させる問題が頻出します。「出現頻度が高いデータに短い符号、低いデータに長い符号を割り当てる」という基本原理を問う選択問題もよく出題されます。また、同じくデータ圧縮の手法である「ランレングス符号化（連続する同じデータを『データ＋連続回数』に置き換える方法）」との違いを比較させる問題も狙われやすいため、それぞれの圧縮方式がどのような性質のデータ（文字の偏りが大きいのか、同じ文字が連続しやすいのか）に適しているかを理解しておくことが重要です。
関連する用語
情報の圧縮効率を高めるエントロピー符号化、ハフマン符号の対比としてよく挙げられるランレングス圧縮、ハフマン符号を決定するために使われるデータ構造である二分木などが関連します。