Location : Home > Languages > Perl > Package Title : Algorithm::InversionList

名称

　Algorithm::InversionList - ビット列からインバージョンリストを生成

概要

use Algorithm::InversionList;
my $data = "Random data here";

my $inv = invlist($data);
print "The inversion list is: @$inv\n";

my $out = data_from_invlist($inv);
print "From data [$data] we reconstructed [$out]\n";

説明

　インバージョンリスト（Inversion lists）は0と1のビット列においてそれぞれの位置を格納するデータ構造のことである。データ "111111100" はインバージョンリストで表現すると 0, 7 という数値のリストになる。本モジュールは1から始まり、もし最初の2ビットが0なら、リストの最初の数字は（1が最初に立つビットである）2になる。最後の数値は文字列の長さを示し、それがどこで終わるかを知る。
　インバージョンリストはきわめて有効である。Perl でスカラーやリストを格納する方法や Perl がポートする様々なデータ構造のために、インバージョンリストが有効になるのに要請される正確なビット列長に対する決定的な規則はない。一般的に、0または1の繰り返しの長いビット列を扱うのであればインバージョンリストを用いるのが適切だろう。
　本モジュールは、検索が速く、２つのリストに対してブール演算が簡単に施せるなどいくつかのよい機能をもったオフセット形式（an offset-based format）で格納している。

エクスポート

invlist($DATA):

　スカラーのデータ列からインバージョンリストを生成する。

data_from_invlist(@LIST):

　インバージョンリストから元データを生成する。

著者

　Teodor Zlatanov, <tzz@lifelogs.com>

参考資料

　perl

【訳注と解説】

1. この説明だけを読んだのではよくわからない、というのが正直なところだと思いますが、作者自身による記事（「洗練されたPerl: PerlでのInversionリスト」 IBM DeveloperWorks）を見つけたので、そちらを読むとよい。
2. 上の記事を読んでもらうとわかると思いますが、ようするにこれはビット列上で1の始まる箇所を記録することでデータを圧縮しようというアルゴリズム。
元データが "111111100" だと、最初に1が来ているので、インバージョンリストにはまず0を格納。次に元リストで変化が起こる（＝1でないものがくる＝0がくる）のは7ビット目なので、リストには7を格納。そしてそれで最後まで変化がないのでリストは {0, 7} で終わり、というわけ。
3. ところが、そうすると「最後の数値は文字列の長さを示し（The last number will always be the length of the string, ）」の部分がそのままでは意味不明。要検討。

Updated : 2006/06/24