ハフマン符号化アルゴリズムとは？基本原理とC++実装をわかりやすく解説

ハフマン符号化（Huffman Coding）は、データを一切失うことなく元の状態に復元できる「可逆圧縮」を実現する、代表的なデータ圧縮アルゴリズムです。このアルゴリズムでは、入力された各文字に対して可変長の符号を割り当てます。符号の長さは文字の使用頻度と密接に関連しており、出現頻度の高い文字ほど短い符号を、出現頻度の低い文字ほど長い符号を受け取ります。これにより、データ全体のサイズを効率的に削減できます。

ハフマン符号化の基本的な流れ

ハフマン符号化の処理は、主に以下の2つの段階で構成されます。

• ハフマン木（Huffman Tree）の構築：各文字の出現頻度をもとに、優先度付きキューを使って二分木を構築します。
• 木の走査による符号の割り当て：構築した木を根から葉へと辿り、左側に「0」、右側に「1」を対応させることで、各文字の符号を決定します。

具体例として、文字列「YYYZXXYYX」を考えてみましょう。この文字列では、文字Yの出現頻度が最も高く、次いでX、そしてZが最も低くなります。したがって、Yに割り当てられる符号はXよりも短くなり、Xの符号はZよりも短くなります。

各文字の出現頻度に基づいて符号を割り当てる処理の計算量は、O(n log n)です。

入力と出力の例

Input:
さまざまな文字を含む文字列（例：「ACCEBFFFFAAXXBLKE」）

Output:
各文字に割り当てられた符号：
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

アルゴリズムの詳細

huffmanCoding(string)

入力：さまざまな文字を含む文字列
出力：各文字に割り当てられた符号

Begin
    ハフマン木用のノードを定義する（文字・頻度・左の子・右の子を持つ構造）
    各文字の頻度を格納するリスト「freq」を作成し、初期値をすべて0にする
    文字列内の各文字cに対して
        freqリスト内の該当文字chの頻度を増加させる
    done

    すべての種類の文字chに対して
        chの頻度が0でなければ
            chとその頻度をノードとして優先度付きキューQに追加する
    done

    Qが空になるまで繰り返し
        Qから要素を取り出し、ノードの左の子として設定する
        Qから要素を取り出し、ノードの右の子として設定する
        ノードを走査して割り当てられた符号を求める
    done
End

traverseNode(n: node, code)

入力：ハフマン木のノードn、および前回の呼び出しから引き継いだ符号
出力：各文字に割り当てられた符号

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

C++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。標準ライブラリの優先度付きキュー（priority_queue）を利用してハフマン木を構築しています。

#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) { // 2つの子ノードから親ノードを生成
        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] != 0)
            qu.push(node((char)i, frequency[i])); // 頻度が0でない文字をキューに追加
    }

    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(); // 根から走査して符号を出力
}

int main() {
    string str = "ACCEBFFFFAAXXBLKE";
    huffmanCoding(str);
    return 0;
}

実行結果

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

まとめ

ハフマン符号化は、文字の出現頻度に応じて可変長の符号を割り当てることで、可逆的なデータ圧縮を実現する古典的かつ強力なアルゴリズムです。ZIPやJPEGなど、多くの圧縮技術の基盤としても採用されており、アルゴリズム学習においても押さえておきたい重要なトピックの一つといえます。