ハフマン符号化 Huffman encoding
2006.06.11 21:58 貪欲法
ファイル圧縮 File compression
これから紹介する Greedy algorithm は、コミュニケーションシステムなどで扱われるデータの "情報量" を圧縮するために考案された符号化法 (encoding method) に関するものです。
一般的に、コンピュータで扱うファイルは冗長性を持っています。符号化は、ファイルは比較的少ない情報量しか持っていないという事実を利用し、ファイルを圧縮します。これらのテクニックは、主にテキストファイル、画像（ラスターイメージ）、サウンドのデジタルデータ、などに適用されます。
ランレングス符号化 Run-length encoding
テキストファイルにおける最も簡単な冗長性の１つが、同じ文字の（長い）繰り返しです。例えば、
という文字列（アルファベットのみ）は、同じ文字の繰り返しからなる部分文字列を、[文字の出現回数、該当する文字] に置き換えることで、よりコンパクトに符号化することができます。
これを、ランレングス符号化 (Run-length encoding) といいます。この符号化は、文字の繰り返しが多い２値のファイルに対しては効率的ですが、通常のテキストファイルに対しては効率的ではありません。なぜなら、繰り返し文字がある箇所でしか圧縮されないからです。
可変長符号化 Variable-length encoding
素朴な符号化を考えてみましょう。以下のように各アルファベットに 5 bits のバイナリコードが割り当てられていると仮定すると、
| A | → | 00000 | (0) |
| B | → | 00001 | (1) |
| C | → | 00010 | (2) |
| . | . | . | . |
| . | . | . | . |
| Z | → | 11001 | (25) |
文字列 "SARASARAHAIR" は
と符号化されます（計 60 bits）。この符号を復号化することはとても簡単で、5 bits づつ読み取り、上記のテーブルに従って各文字を変換します。
ここで注目すべきことが、この文字列 "SARASARAHAIR" は、H は 1 回のみ、A は 5 回も出現しているにもかかわらず、どちらも 5 bits づつ割り当てられているということです。この符号をより短くするためのアイデアの１つが、最も多く出現する文字に最も短いビット列を割り当てることです。
可変長符号化 (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" は
と符号化することができます。これは、16 bits しか必要とせず、前の素朴な方法（60 bits）に比べるとかなり圧縮されていますが、実際のコードには成り得ません。なぜなら、復号化される文字列がビット列の区切りに依存してしまい一意に決まらないからです。例えば、上記の符号 0101001010100111 は、"ARARAAHHHARRR" や "SSASSSASI" など様々な文字列に変換できてしまうのです。しかし、以下のように特別な区切り文字 (delimiter) を用いたとしても、素朴な方法と比べれば符号の長さはコンパクトと言えるでしょう。
次は、文字列を区切り文字を用いずにコンパクトに符号化する方法を考えてみましょう。
もし、各文字に対応するビット列が、他のどの文字に対応するビット列の接頭語（prefix）になっていなければ、区切り文字が必要ないことが分かります。例えば、以下のようにビット列を割り当てると、
| A → 11 | H → 00 | I → 010 | R → 10 | S → 011 |
"SARASARAHAIR" は
のように符号化されますが、復号化は一意に決まります（確認してみましょう）。
このような符号を生成するための簡単な方法の１つが、符号をバイナリツリーで表現することです。M 個の葉を持つ任意のバイナリツリーは、M 個（種類）の異なる文字を含む文字列を符号化するために用いることができます。このとき、ツリーの各葉を各文字に対応させます。各文字の符号は、ツリーの根から対応する葉へのパスによって決定します。このとき、左へ向かった場合 0、右へ向かった場合 1 とします。例えば、以下の２つのツリーは、"SARASARAHAIR" の符号を与えます。
| ツリー 1 | ツリー 2 | |||||||||||
 |
 |
|||||||||||
|
|
このバイナリツリー表現は、どの文字に対応するビット列も他の文字に対応するビット列の接頭語にならないことを保障します。従って、生成された符号は、一意的に復号化されます。
ここで問題となるのが、符号化するためにどちらのバイナリツリーを用いるべきか？です。各ツリーを用いて "SARASARAHAIR" を符号化してみましょう。
| ツリー 1 → 00010011010000100110101001011011 |
| ツリー 2 → 1100100110010011100111110 |
ツリー 2 の方が短い符号を与えます。このように、与えられた任意の文字列に対して、最も短い符号を導くバイナリツリーを生成するためのアルゴリズムが D. Huffman が考案した ハフマン符号化（Huffman encoding）です。
ハフマン符号化 Huffman encoding
バイナリツリーを生成するために、ハフマン符号化は貪欲法（Greedy algorithm）を用います。このツリーをハフマン木と呼びます。ハフマン木に含まれるノードの集合を S とすると、ハフマン符号化は以下のように動作します。
| 1. | 与えられた文字列に含まれる各文字の出現頻度を計算します。各文字に対応するノードをつくり、S に追加します。この時、これらのノードに、対応する文字の出現頻度を"重み"として割り当てます。 |
| 2. | S から重みが最も低い２つのノードを取り出し、それらを子とする新しい親ノード（ルート）を作り S に追加します。この時、親ノードの重みとして、選ばれた２つの子の重みの和を割り当てます。 |
| 3. | 2. の処理を S のサイズが 1 になるまで繰り返します。 |
与えられた文字列 "AAABCCXYZ" をハフマン符号化した様子を下図に示します。初期状態は S = {A, B, C, X, Y, Z} です。各ノードの ID を対応する文字の ASCIIコード にします。ただし、追加されるノードは 256 から始まる整数とします。S に含まれるノードは、緑色の背景を持ちます。
このアルゴリズムによって、より小さい重みをもつ文字がルートから遠ざかり、より大きい重みをもつ文字がルートに近づきます。
実際に各文字に対応するビット列を生成するには、ハフマン木のルートから preorder でツリーを parse します。この時、左の子に向かうとき 0、右の子に向かうとき 1 を記録していきます（以下のプログラムを参照して下さい）。
以下に、ハフマン符号化のプログラム例を示します。バイナリツリーを作る過程で、アルゴリズムは S から重みの最も小さい２つのノードを優先して取り出し、さらに新しいノードを生成し 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) | ↑ページトップ |