ハフマン符号化とは？仕組み・アルゴリズム・C++実装例をわかりやすく解説

ハフマン符号化（Huffman Coding）は、圧縮後に元のデータを完全に復元できる可逆圧縮（ロスレス圧縮）アルゴリズムの一つです。この手法では、入力された各文字に対して可変長のコードを割り当てます。コードの長さは文字の出現頻度と密接に関係しており、出現頻度の高い文字ほど短いコードが与えられ、出現頻度の低い文字にはより長いコードが割り当てられます。

ハフマン符号化の処理は、大きく分けて次の2つの段階で構成されます。

1. ハフマン木（Huffman Tree）の構築
2. 木を走査して各文字にコードを割り当てる

具体例として、文字列「YYYZXXYYX」を考えてみましょう。この文字列では、文字Yの出現頻度が最も高く、次いでX、そしてZが最も低くなります。そのため、コードの長さはYが最も短く、次にX、Zが最も長くなります。

• 文字の出現頻度に基づいてそれぞれのコードを割り当てる処理の計算量はO(n log n)です。

また、ハフマン符号は「どの符号も他の符号の先頭部分（接頭辞）にならない」という接頭辞符号（プレフィックス符号）の性質を持つため、区切り記号がなくても符号列を一意に復号できます。この特性により、ZIP形式などのファイル圧縮やJPEG画像圧縮など、幅広い分野で応用されています。

入力と出力の例

入力 − 異なる文字を含む文字列（例：「ACCEBFFFFAAXXBLKE」）
出力 − 各文字に割り当てられたコード：

Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

この結果を見ると、出現頻度が最も高いF（4回）には最短のコード「01」が、出現頻度が最も低いKとL（各1回）には最長のコード「0000」「0001」が割り当てられていることがわかります。

アルゴリズム

huffmanCoding(string)

入力 − 異なる文字を含む文字列

出力 − 各文字に割り当てられたコード

Begin
    ハフマン木用に、文字・頻度・左の子・右の子を持つノードを定義する
    各文字の頻度を格納するリスト「freq」を作成し、初期値をすべて0にする
    文字列中の各文字cについて
        freqリスト内の該当文字の頻度を1増やす
    繰り返し終了
    すべての種類の文字chについて
        chの頻度が0以外であれば、chとその頻度を優先度付きキューQのノードとして追加する
    繰り返し終了
    Qが空になるまで以下を繰り返す
        Qから要素を1つ取り出し、ノードの左の子に代入する
        Qからさらに要素を取り出し、ノードの右の子に代入する
        ノードを走査して各文字に割り当てるコードを求める
    繰り返し終了
End

traverseNode(n: node, code)

入力 − ハフマン木のノードn、および前回の呼び出しから引き継いだコード

出力 − 各文字に割り当てられたコード

if ノードnの左の子 ≠ φ then
    traverseNode(左の子(n), code+'0')  // 左の子をたどる
    traverseNode(右の子(n), code+'1')  // 右の子をたどる
else
    現在のノードの文字とデータを表示する

C++による実装例

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
    int freq;
    char data;
    const node *child0, *child1;
    node(char d, int f = -1){ //ノードに値を設定する
        data = d;
        freq = f;
        child0 = NULL;
        child1 = NULL;
    }
    node(const node *c0, const node *c1){
        data = 0;
        freq = c0->freq + c1->freq;
        child0 = c0;
        child1 = c1;
    }
    bool operator<( const node &a ) const { //<演算子はキュー内の優先度決定に使用される
        return freq >a.freq;
    }
    void traverse(string code = "")const{
        if(child0!=NULL){
            child0->traverse(code+'0'); //左の子なのでコードに0を追加
            child1->traverse(code+'1'); //右の子なのでコードに1を追加
        }else{
            cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl;
        }
    }
};
void huffmanCoding(string str){
    priority_queue<node> qu;
    int frequency[256];
    for(int i = 0; i<256; i++)
        frequency[i] = 0; //すべての頻度を初期化
    for(int i = 0; i<str.size(); i++){
        frequency[int(str[i])]++; //出現頻度をカウント
    }
    for(int i = 0; i<256; i++){
        if(frequency[i]){
            qu.push(node(i, frequency[i]));
        }
    }
    while(qu.size() >1){
        node *c0 = new node(qu.top()); //左の子を取得し、キューから削除
        qu.pop();
        node *c1 = new node(qu.top()); //右の子を取得し、キューから削除
        qu.pop();
        qu.push(node(c0, c1)); //2つの子の頻度を合計したノードをキューに戻す
    }
    cout << "The Huffman Code: " << endl;
    qu.top().traverse(); //木を走査してコードを取得
}
main(){
    string str = "ACCEBFFFFAAXXBLKE"; //頻度を求める対象の文字列
    huffmanCoding(str);
}

実行結果

The Huffman Code:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111