fc2ブログ



ハフマン符号化 Huffman encoding

2006.06.11 21:58  貪欲法

ファイル圧縮 File compression
これから紹介する Greedy algorithm は、コミュニケーションシステムなどで扱われるデータの "情報量" を圧縮するために考案された符号化法 (encoding method) に関するものです。

一般的に、コンピュータで扱うファイルは冗長性を持っています。符号化は、ファイルは比較的少ない情報量しか持っていないという事実を利用し、ファイルを圧縮します。これらのテクニックは、主にテキストファイル、画像(ラスターイメージ)、サウンドのデジタルデータ、などに適用されます。

ランレングス符号化 Run-length encoding
テキストファイルにおける最も簡単な冗長性の1つが、同じ文字の(長い)繰り返しです。例えば、

AAAAAABBBCCAADDDDABCBBBCCCCCC

という文字列(アルファベットのみ)は、同じ文字の繰り返しからなる部分文字列を、[文字の出現回数、該当する文字] に置き換えることで、よりコンパクトに符号化することができます。

6A3B2C2A4DABC3B6C

これを、ランレングス符号化 (Run-length encoding) といいます。この符号化は、文字の繰り返しが多い2値のファイルに対しては効率的ですが、通常のテキストファイルに対しては効率的ではありません。なぜなら、繰り返し文字がある箇所でしか圧縮されないからです。

可変長符号化 Variable-length encoding
素朴な符号化を考えてみましょう。以下のように各アルファベットに 5 bits のバイナリコードが割り当てられていると仮定すると、

A 00000 (0)
B 00001 (1)
C 00010 (2)
. . . .
. . . .
Z 11001 (25)

文字列 "SARASARAHAIR" は

100100000010001000001001000000100010000000111000000100010001

と符号化されます(計 60 bits)。この符号を復号化することはとても簡単で、5 bits づつ読み取り、上記のテーブルに従って各文字を変換します。

ここで注目すべきことが、この文字列 "SARASARAHAIR" は、H は 1 回のみ、A は 5 回も出現しているにもかかわらず、どちらも 5 bits づつ割り当てられているということです。この符号をより短くするためのアイデアの1つが、最も多く出現する文字に最も短いビット列を割り当てることです。

可変長符号化 (Variable-length encoding) では、各文字に一定のビット列を割り当てる代わりに、テキスト内でより多く出現する文字により短いビット列を、より稀に出現する文字により長いビット列を割り当てます。

試しに、"SARASARAHAIR" では、A が 5 回、H が 1 回、I が 1 回、R が 3 回、S が 2 回、それぞれ出現するので、上記のアイデアから以下のようにビット列を割り当ててみましょう。

A → 0 H → 10 I → 11 R → 1 S → 01

このコードを用いて、"SARASARAHAIR" は

0101001010100111

と符号化することができます。これは、16 bits しか必要とせず、前の素朴な方法(60 bits)に比べるとかなり圧縮されていますが、実際のコードには成り得ません。なぜなら、復号化される文字列がビット列の区切りに依存してしまい一意に決まらないからです。例えば、上記の符号 0101001010100111 は、"ARARAAHHHARRR" や "SSASSSASI" など様々な文字列に変換できてしまうのです。しかし、以下のように特別な区切り文字 (delimiter) を用いたとしても、素朴な方法と比べれば符号の長さはコンパクトと言えるでしょう。

01-0-1-0-01-0-1-0-10-0-11-1

次は、文字列を区切り文字を用いずにコンパクトに符号化する方法を考えてみましょう。

もし、各文字に対応するビット列が、他のどの文字に対応するビット列の接頭語(prefix)になっていなければ、区切り文字が必要ないことが分かります。例えば、以下のようにビット列を割り当てると、

A → 11 H → 00 I → 010 R → 10 S → 011

"SARASARAHAIR" は

011111011011111011001101010

のように符号化されますが、復号化は一意に決まります(確認してみましょう)。

このような符号を生成するための簡単な方法の1つが、符号をバイナリツリーで表現することです。M 個の葉を持つ任意のバイナリツリーは、M 個(種類)の異なる文字を含む文字列を符号化するために用いることができます。このとき、ツリーの各葉を各文字に対応させます。各文字の符号は、ツリーの根から対応する葉へのパスによって決定します。このとき、左へ向かった場合 0、右へ向かった場合 1 とします。例えば、以下の2つのツリーは、"SARASARAHAIR" の符号を与えます。

ツリー 1 ツリー 2
encode1.gif
encode2.gif
A → 010
H → 10
I → 11
R → 011
S → 00
A → 0
H → 1110
I → 1111
R → 10
S → 110

このバイナリツリー表現は、どの文字に対応するビット列も他の文字に対応するビット列の接頭語にならないことを保障します。従って、生成された符号は、一意的に復号化されます。

ここで問題となるのが、符号化するためにどちらのバイナリツリーを用いるべきか?です。各ツリーを用いて "SARASARAHAIR" を符号化してみましょう。

ツリー 1 → 00010011010000100110101001011011
ツリー 2 → 1100100110010011100111110

ツリー 2 の方が短い符号を与えます。このように、与えられた任意の文字列に対して、最も短い符号を導くバイナリツリーを生成するためのアルゴリズムが D. Huffman が考案した ハフマン符号化(Huffman encoding)です。

ハフマン符号化 Huffman encoding
バイナリツリーを生成するために、ハフマン符号化は貪欲法(Greedy algorithm)を用います。このツリーをハフマン木と呼びます。ハフマン木に含まれるノードの集合を S とすると、ハフマン符号化は以下のように動作します。

1. 与えられた文字列に含まれる各文字の出現頻度を計算します。各文字に対応するノードをつくり、S に追加します。この時、これらのノードに、対応する文字の出現頻度を"重み"として割り当てます。
2. S から重みが最も低い2つのノードを取り出し、それらを子とする新しい親ノード(ルート)を作り S に追加します。この時、親ノードの重みとして、選ばれた2つの子の重みの和を割り当てます。
3. 2. の処理を S のサイズが 1 になるまで繰り返します。

与えられた文字列 "AAABCCXYZ" をハフマン符号化した様子を下図に示します。初期状態は S = {A, B, C, X, Y, Z} です。各ノードの ID を対応する文字の ASCIIコード にします。ただし、追加されるノードは 256 から始まる整数とします。S に含まれるノードは、緑色の背景を持ちます。

huffman.gif

このアルゴリズムによって、より小さい重みをもつ文字がルートから遠ざかり、より大きい重みをもつ文字がルートに近づきます。

実際に各文字に対応するビット列を生成するには、ハフマン木のルートから preorder でツリーを parse します。この時、左の子に向かうとき 0、右の子に向かうとき 1 を記録していきます(以下のプログラムを参照して下さい)。

以下に、ハフマン符号化のプログラム例を示します。バイナリツリーを作る過程で、アルゴリズムは S から重みの最も小さい2つのノードを優先して取り出し、さらに新しいノードを生成し S に追加していきます。従って S のデータ構造として優先順位キュー(Priority queue)を使うことは明白です。優先順位キューを用いた場合のハフマン符号化のオーダーは O(nlonn) となります。

// @author yutaka C++
#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>

using namespace std;

#define CHAR_SIZE 256
#define NODE_SIZE 512
#define TOLEFT '0'
#define TORIGHT '1'

class Node{
    public:
    int id, weight, left, right;
    Node(){ weight = 0; }
    Node( int id, int w, int l, int r ): id(id), weight(w), left(l), right(r){}
    
    bool operator < ( const Node &n ) const{
        return weight > n.weight;
    }
};

Node nodes[NODE_SIZE];
int newRootId;

void recursive( int id, string code ){
    if ( id < CHAR_SIZE ){
        printf("%c  %s\n", id, code.c_str()); return;
    }
    recursive( nodes[id].left, code + TOLEFT );
    recursive( nodes[id].right, code + TORIGHT );
}

// input the string to be encoded
void encoding( string text ){
    int w[CHAR_SIZE];
    
    // Compute the weight of each character
    for ( int i = 0; i < CHAR_SIZE; i++ ) w[i] = 0;
    for ( int i = 0; i < text.size(); i++ ) w[text[i]]++;
    
    // Output w[]
    for ( int i = 0; i < CHAR_SIZE; i++ ){
        if ( w[i] ) printf("%c : %d times\n", i, w[i]);
    }
    
    // Construct and initialize the priority queue
    priority_queue<Node> PQ;
    for ( int i = 0; i < CHAR_SIZE; i++ ) {
        if ( w[i] > 0 ){
            Node node = Node( i, w[i], -1, -1 );
            PQ.push( node );
            nodes[ node.id ] = node;
        }
    }
    
    // Construct the binary tree
    newRootId = CHAR_SIZE;
    
    while ( PQ.size() > 1 ){
        Node left = PQ.top(); PQ.pop();
        Node right = PQ.top(); PQ.pop();
        int weight = left.weight + right.weight;
        Node newRoot = Node( newRootId, weight, left.id, right.id );
        PQ.push( newRoot );
        nodes[ newRootId++ ] = newRoot;
    }
    
    // Output the binary tree constructed
    for ( int i = newRootId - 1; i >= CHAR_SIZE; i-- ){
        if ( nodes[i].left >= CHAR_SIZE )
        printf("left  son of %4d is %4d\n", i, nodes[i].left );
        else
        printf("left  son of %4d is %4c\n", i, nodes[i].left );
        if ( nodes[i].right >= CHAR_SIZE )
        printf("right son of %4d is %4d\n", i, nodes[i].right );
        else
        printf("right son of %4d is %4c\n", i, nodes[i].right );
    }
}

void decoding(){
    recursive( newRootId - 1, "");
}

main(){
    string text; cin >> text;
    encoding( text );
    decoding();
}

Sample Input

SARASARAHAIR

Sample Output

A : 5 times
H : 1 times
I : 1 times
R : 3 times
S : 2 times
left  son of  259 is    A
right son of  259 is  258
left  son of  258 is    R
right son of  258 is  257
left  son of  257 is    S
right son of  257 is  256
left  son of  256 is    H
right son of  256 is    I
A  0
R  10
S  110
H  1110
I  1111




スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




貪欲法 Greedy algorithms

2006.06.06 17:17  貪欲法

"Greedy" とは、食べ物や飲み物などに対する強い "欲求" や "欲望" を意味しますが、Greedy algorithms (貪欲アルゴリズム、よくばり法)では、この食べ物や飲み物をアルゴリズムで扱うデータと見なすことができます。

一般的に、最適化問題 (optimazation problems) のためのアルゴリズムの多くは、あるデータの "選択" の繰り返しという構造になっています。Greedy algorithms は、各計算ステップで、局所的に最適(その時点で最も最適と思われるもの)な選択を繰り返し、最終的に大域的な最適解を求める方法です。

すでに紹介したものも含めて、以下のように Greedy algorithms は多くの問題に対して、最適解を求めることができます。このセクションでは、これらの問題と対応するアルゴリズムを紹介します。

随時追加予定です。


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |