Title : Algorithm::Huffman
|
Location : Home > Languages > Perl > Package Title : Algorithm::Huffman |
|
Algorithm::Huffman - ハフマンアルゴリズムの実装
use Algorithm::Huffman;
my %char_counting = map {$_ => int rand(100)} ('a' .. 'z', 'A' .. 'Z');
# または文字を数えるもの。
# ハフマンアルゴリズムは乱数には適さない。 :-))
my $huff = Algorithm::Huffman->new(\%char_counting);
my $encode_hash = $huff->encode_hash;
my $decode_hash = $huff->decode_hash;
my $encode_of_hello = $huff->encode_bitstring("Hello");
print "Look at the encoding bitstring of 'Hello': $encode_of_hello\n";
print "The decoding of $encode_of_hello is '", $huff->decode_bitstring($encode_of_hello), "'";
本モジュールはハフマンアルゴリズム（huffman algorithm）を実装している。
目的は所与の異なる文字（文字列）とその発生回数に対するよいコードを提供することである。
詳しくはデータ圧縮に関する本を参照のこと。
しかしながらアルゴリズムは極めて単純である。
ヒープ（キーは文字または文字列とし、値はその発生回数とする）があるとしよう。アルゴリズムの各段階では最も数の少ない２つの文字に着目する。そしてそれぞれに添字（一方を 0 、他方を 1 とする。これらは統合され、足しあわされた発生回数を持つヒープの１つの要素として見なす。この結合でツリーは成長し、ヒープは減っていく。
例を見てみよう。文字とその発生回数が与えられているものとする。
a (15) b(7) c(6) d(6) e(5)
最初の段階では e 及び d が最も稀な文字であるので以下のようなヒープとツリー構造となる。
a(15) de(11) b(7) c(6)
de
/ \
"0"/ \"1"
d e
次の段階では
a(15) bc(13) de(11)
de bc
/ \ / \
"0"/ \"1" "0"/ \"1"
d e b c
次の段階では
a(15) bcde(24)
bcde
/ \
"0"/ \"1"
/ \
de bc
/ \ / \
"0"/ \"1" "0"/ \"1"
d e b c
次の段階では残りが結合して
Huffman-Table
/ \
"0"/ \"1"
/ \
/ \
bcde a
/ \
"0"/ \"1"
/ \
de bc
/ \ / \
"0"/ \"1" "0"/ \"1"
d e b c
最終的に以下のような表が得られる。
a 1 b 010 c 011 d 000 e 001
ツリーの左に行くか右に行くかでどのように値を割り振るかについては規則はないので、以下のようにもコードを与えることができる。
a 0 b 100 c 101 d 110 e 111
$huff = Algorithm::Huffman->new( HASHREF )
文字の発生回数を所与として新たなハフマン表を生成する。
キーは所与の文字または文字列のハッシュ参照であり、値はその発生回数である。
ハッシュ参照が用いられると、そのハッシュはきわめて大きなものになる。（あらゆる３文字の組み合わせ）
渡されるハッシュは最低２要素から構成されねばならない。これはハフマンアルゴリズムが１または０を用いて表現されるからである。２つの要素の一方は 0 、他方は 1 として表現される。
集計は（数えるハッシュにおける値として与えられている）０以上でなければならない。負の値は意味をなさない。ある文字または文字列が０個であればコード化されている。特に大規模テキストをコード化するような状況を考えてのことである。全文字または文字列の集計のよい仮定を得るためにこの大規模テキスト（または辞書から）の最初の部分の共通部分文字列を数える。いくつかのアスキー文字（例えば英文字における a-ウムラウト）は起きなかった。全テキストがコード化可能であることを確認するためには数えられていない全文字を０にすることである。これらのエンコード／デコード ビット列があれば存在していることを保証する。これらのビット列は数えられた文字または文字列のあらゆる他のエンコード／デコード列よりも長くないことが保証されている。集計は整数でなくてもよく、小数でもよい。（パーセントなど）
$huff->encode_hash
エンコードするハッシュへの参照を返す。エンコードするハッシュのキーはコンストラクト時に渡される文字または文字列であり、値はそのビット表現である。0及び1からなる文字列のビット表現は２進数の値ではないことに注意すること。
$huff->decode_hash
デコードするハッシュへの参照を返す。デコードするハッシュのキーはビット表現であり、値はビット列が意味する文字または文字列である。0及び1からなる文字列のビット表現は２進数の値ではないことに注意すること。
$huff->encode_bitstring($string)
所与の文字列の（現在のハフマンツリーによって）エンコード化されたものを表す '1' 及び '0' のビット列を返す。
これは少々あいまいさを残しており、ハフマンツリーの中に 'e' があるのか 'er' があるのかを判別できないことがある。このアルゴリズムは欲張り（greedy）である。所与の文字列は最初とあらゆるループにおいて横断され、ハフマンツリーから可能な最長のエンコード結果を求める。ここでは 'e' の代わりに 'er' とみなされる場合がある。
欲張り法は将来のバージョンで用いるかどうかは保証の限りではない。（例えば、ハフマンツリーから次の２つ（またはn個の）可能な部分文字列をエンコード化し、最短のエンコード化ビット列を選択するようなものを考えている。）
$huff->encode($string)
$string のエンコード化されパック化されたハフマンビットベクトルを返す。詳しくは encode_bitstring の記述を見よ。
$huff->decode_bitstring($bitstring)
'1' 及び '0' のビット列を元の文字列にデコードする。エンコードは多少の曖昧さはあるが、デコードは常に一義的である。１または０だけからなるビット列であることに注意すること。そうでなければ落ちる。
ビット列が不完全な場合も落ちる。例えば以下のようなハフマン表が与えられているとしよう。
a => 1 b => 01 c => 00
コード 'abc' がほしいのであるが、正しいコード化は '10100' である。しかし '1010' （最後の 0 は欠落）に対してはエラーメッセージ Unknown bit sequence starting at index 3 in the bitstring が出力される。
$huff->decode($bitvector)
パック化されたビットベクトル（ ->encode メソッドでエンコードされたもの）をデコードする。詳しくは decode_bitstring の説明を見よ。
デフォルトではなし。
文字または文字列が１度も発生しなければコード化されている。そのようなときには事前に grep すべきである。私はこれを変更するつもりはなく、重要な役に立つことがあると思っている。（ある英文において発見されたあらゆる3文字の組み合わせをコード化することを、しかも全てのアスキー文字をコード化し、しかもそこに解析したものが現れなかったと想像してみて欲しい。それらが他のテキストで発生し、失われた情報なしに全テキストをコード化できる保証を与えなければならない。)
もしユーザのストリームを分割するために部分をコード化するならば、以下のようにするとよい。
my $encode1 = $huff->encode_bitstring($chapter1); my $encode2 = $huff->encode_bitstring($chapter2); my $total_encode = $encode1 . $encode2; my $all_chapters = $huff->decode_bitstring($total_encode); # Now $all_chapter eq $chapter1 . $chapter2
これはうまく稼動する。しかし ..code_bitstring methods を ..code メソッドで置き換えるとうまく稼動しない。文字または文字列の大規模なヒストグラムではテストしていないその他の点でも、まだこのコードはアルファ版である。
これまで私は処理速度に配慮していなかった。
いくつかは Perl においても改良するかも知れないが、大半は C での再実装を行う。
パラメータ妥当性と概要に関する問題を指摘してくれた Perry Leopold に謝意を表明する。
データ圧縮に関するあらゆるよい本
Janek Schleicher, <bigj@kamelfreund.de>
Copyright 2002 by Janek Schleicher
本ライブラリはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。
訳注というか言い訳
申し訳ないが、このドキュメントの英文は構文や言い回しがよくわからない。。。。
|
|
Updated : 2007/05/12 |