ソートされた入力に対する効率的なハフマン符号化アルゴリズム(O(n))とC++実装

はじめに

以前のハフマン符号化の問題では、頻度のリストはソートされていませんでした。しかし、頻度のリストがあらかじめソートされた順序で与えられている場合は、符号の割り当て処理をより効率的に行うことができます。

この手法では、2つの空のキューを使用します。まず、一意な文字ごとに葉ノードを作成し、頻度の昇順でキューに挿入していきます。

このアプローチにより、アルゴリズムの計算量はO(n)に抑えられます。

なぜ2つのキューでO(n)が実現できるのか

通常のハフマン符号化では優先度付きキュー(ヒープ)を利用するため、計算量はO(n log n)となります。一方、頻度がソート済みであれば、次のような仕組みで高速化できます。

• キュー1: ソート済みの葉ノード(文字とその頻度)を昇順で保持
• キュー2: ノード同士の結合によって生成された内部ノード(部分木)を保持

2つの最小ノードを結合して新しく作られるノードの頻度は、既に生成済みのどの内部ノードの頻度以上になるため、キュー2は自然に昇順が保たれます。したがって、両キューの先頭要素を比較するだけで常に最小のノードを取り出すことができます。各操作が定数時間で完了するため、全体の計算量はO(n)になります。

入力と出力

入力:
ソート済みの文字とその頻度
文字: {L, K, X, C, E, B, A, F}
頻度: {1, 1, 2, 2, 2, 2, 3, 4}

出力:
各文字に割り当てられた符号
L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

アルゴリズム

huffmanCodes(dataList, freqList, n)

入力: データのリスト、頻度のリスト、データ数n
出力: 各文字に割り当てられた符号

Begin
    root := huffmanTree(dataList, freqList, n)
    // ハフマン木の根を作成し、符号を格納する配列と先頭ポインタを用意する
    getCodes(root, array, top) を呼び出して各文字の符号を求める
End

getCodes(root: node, array, top)

入力: 根ノード、符号を格納する配列、配列の先頭位置
出力: 各文字の符号

Begin
    if leftChild(root) ≠ φ then
        array[top] := 0
        getCodes(leftChild(root), array, top)
    if rightChild(root) ≠ φ then
        array[top] := 1
        getCodes(rightChild(root), array, top)
    if leftChild(root) = φ かつ rightChild(root) = φ then
        根ノードの文字 ch を表示する
        配列のすべての要素について
            文字 ch に対応する array[i] の符号を表示する
        done
End

huffmanTree(dataList, freqList, n)

入力: データのリスト、頻度のリスト、データ数n
出力: 構築されたハフマン木

Begin
    すべての異なる文字 ch について
        文字 ch とその頻度を持つノードをキュー q1 に追加する
    done

    while q1 が空でない または q2 のサイズ ≠ 1 do
        q1 と q2 を使って最小の2つのノードを見つけ、
        新しいノードの左の子と右の子として追加する
        新しいノードを q2 に追加する
    done

    q2 からノードを取り出し、そのノードを返す
End

C++による実装例

#include<iostream>
#include<queue>
using namespace std;

struct node {
    char data;
    int freq;
    node *child0, *child1;
};

node *getNode(char d, int f) {
    node *newNode = new node;
    newNode->data = d;
    newNode->freq = f;
    newNode->child0 = NULL;
    newNode->child1 = NULL;
    return newNode;
}

node *findMinNode(queue<node*>&q1, queue<node*>&q2) {
    node *minNode;
    if(q1.empty()) { //最初のキューが空なら、2番目のキューからノードを取り出して返す
        minNode = q2.front();
        q2.pop();
        return minNode;
    }

    if(q2.empty()) { //2番目のキューが空なら、最初のキューからノードを取り出して返す
        minNode = q1.front();
        q1.pop();
        return minNode;
    }

    if((q1.front()->freq) < (q2.front()->freq)) { //2つのキューの先頭から小さい方を選ぶ
        minNode = q1.front();
        q1.pop();
        return minNode;
    }else {
        minNode = q2.front();
        q2.pop();
        return minNode;
    }
}

node *huffmanTree(char data[], int frequency[], int n) {
    node *c0, *c1, *par;
    node *newNode;
    queue<node*> qu1, qu2;

    for(int i = 0; i<n; i++) { //すべてのノードをキュー1に追加
        newNode = getNode(data[i], frequency[i]);
        qu1.push(newNode);
    }

    while(!(qu1.empty() && (qu2.size() == 1))) {
        c0 = findMinNode(qu1, qu2); //最小の2つのノードを子として取得
        c1 = findMinNode(qu1, qu2);
        node *newNode = getNode('#', c0->freq+c1->freq);

        //中間ノードには特殊文字を設定
        par = newNode;
        par->child0 = c0;
        par->child1 = c1;
        qu2.push(par); //部分木をキュー2に追加
    }

    node *retNode = qu2.front();
    qu2.pop();
    return retNode;
}

void getCodes(node *rootNode, int array[], int n) {  //符号を格納する配列
    if(rootNode->child0 != NULL) {
        array[n] = 0;
        getCodes(rootNode->child0, array, n+1);
    }

    if(rootNode->child1 != NULL) {
        array[n] = 1;
        getCodes(rootNode->child1, array, n+1);
    }

    if(rootNode->child0 == NULL && rootNode->child1 == NULL) {  //根が葉ノードの場合
        cout << rootNode->data << ": ";

        for(int i = 0; i<n; i++)
            cout << array[i];
        cout << endl;
    }
}

void huffmanCodes(char data[], int frequency[], int n) {
    node *rootNode = huffmanTree(data, frequency, n);
    int array[50], top = 0;
    getCodes(rootNode, array, top);
}

int main() {
    char data[] = {'L', 'K', 'X', 'C', 'E', 'B', 'A', 'F'};
    int frequency[] = {1, 1, 2, 2, 2, 2, 3, 4};
    int n = sizeof(data)/sizeof(data[0]);
    huffmanCodes(data, frequency, n);
}

実行結果

L: 0000
K: 0001
X: 001
C: 010
E: 011
F: 10
B: 110
A: 111

まとめ

頻度リストがソート済みであることを活かし、ヒープの代わりに2つのキュー(FIFO)を使うことで、ハフマン木の構築を線形時間O(n)で行うことができました。木の左の子に0、右の子に1を割り当てて根から葉まで辿ることで、各文字固有の接頭辞符号が得られます。頻度の高い文字ほど木の浅い位置に配置され、短い符号が割り当てられるという、ハフマン符号化の基本的な性質も保たれています。