perlによる大規模データの取扱い

本ページでは，perlでどのようにして大規模なデータを保存するかついて説明します．主にスタンドアロンで動くもの (クライアント<->サーバ型でない，いわゆる組込み型) について紹介したいと思います．

Berkeley DB
- BerkeleyDB
- DB_File
SDBM
- SDBM_File
GDBM
- GDBM_File
CDB
- CDB_File
QDBM
- Depot
- Curia
- Villa
TDB
- TDB_File
SQLight
- DBD::SQLite
SUFFIX ARRAY
- SUFARY
- SARY
複雑なデータ構造
- Data::Dumper
- Storable
- MLDBM
いろいろな比較
- ファイルサイズ
- Benchmark
Link
サンプルデータについて

Berkeley DB

Berkeley DBは，組み込み向けデータベースです．通常データベースというとOracleだとかPostgreSQLなどのリレーショナルデータベースを思い浮かべますが，SQLなどの問い合わせ言語を持っていません．キーから値を取り出すような基本的な機能を提供しています．ライブラリとして存在していてC言語をはじめ，さまざなま言語から使用することが出来ます．

現在のバージョンは4.3で，バージョンが上がるごとに機能が拡張されています．Berkeley DBを扱うPerlモジュールはBerkeleyDBとDB_Fileと2種類あります．BerkeleyDB は，バージョン2,3,4で拡張された機能を使えるのに対して，DB_Fileはバージョン1で提供されている機能しか使用できない(バージョン2以上も使用できるがインターフェースはバージョン1のものに限られる) という違いがあります．

BerkeleyDB

Berkeley DBで利用できるほとんどの機能へのインターフェースを提供します．

BerkeleyDB::HASH
TODO
BerkeleyDB::TREE
TODO
BerkeleyDB::RECNO
TODO
BerkeleyDB::QUEUE
TODO

DB_FIle

Berkeley DBバージョン1で提供しているインターフェースのみが使用できます． DB_HASH,DB_TREE,DB_RECNOが利用可能です．

DB_HASH

BerkeleyDB::HASHと違いDB_HASHは，重複したキーを個別に扱うことが出来ません．使用例．

use Fcntl;
use DB_File;

my $file = 'eijiro';
my %db;
unlink "$file.tree";
tie %db, 'DB_File' , "$file.tree", O_RDWR|O_CREAT, 0644, $DB_BTREE or die;
open(FP, "$file.txt") or die;
while (<FP>) {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $db{$key} = $value;
}
close(FP);
untie %db;

O_RDWRなどは，データベースファイルをオープンする際のモードです．

読み込み専用 : O_RDONLY
読み書き両用 : O_RDWR
新規作成 : O_CREAT
読み書き両用、存在しなければ新規作成 : O_RDWR | O_CREAT

0644は新規に作成する際のファイルのパーミッションです．

検索例

use Fcntl;
use DB_File;

my $file = 'eijiro';
tie my %db, 'DB_File', "$file.hash", O_RDONLY, 0644, $DB_HASH or die;

my $key = $ARGV[0];
print $db{$key},"\n" if defined $db{$key};

DB_TREE

DB_TREEはデータ構造に木構造を利用しており，データの順番を保持したまま保存できます．また重複したキーを扱うことが出来ます．ここでは重複を許した使用例を記述します．

use Fcntl;
use DB_File;

my $file = 'eijiro';
my %db;
unlink "$file.tree";
$DB_BTREE->{'flags'} = R_DUP;       # キーの重複を可能にする
tie %db, 'DB_File' , "$file.tree", O_RDWR|O_CREAT, 0644, $DB_BTREE or die;
open(FP, "$file.txt") or die;
while (<FP>) {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $db{$key} = $value;
}
close(FP);
untie %db;

検索例もキーにマッチした全てのバリューを出力するスクリプトにします．

use Fcntl;
use DB_File;

my $file = 'eijiro';
$DB_BTREE->{'flags'} = R_DUP;
my $x = tie my %db, 'DB_File' , "$file.tree", O_RDONLY, 0644, $DB_BTREE or die;

my $key = $ARGV[0];
foreach ( $x->get_dup($key)) {
    print $_, "\n";
}

DB_RECNO
TODO
キャッシュサイズについて
TODO

SDBM

SDBMは，由来はよくわかりませんが昔から存在するDBMです．ただしデータサイズに制限があり，キーとバリューを併せて1008バイトまでです．英辞郎のDB を作成しようとすると制限を超えてしまうエントリーがあるので，その場合は，バリューを強制的に切り捨てます．しかしそれでもエラーがでる．よくよく調べるとハッシュキーが重複した場合，両方とも1つのエントリーとして扱われて1008バイトの制限に引っかかってしまうようです．ソースを載せておきます．

#!/usr/bin/perl
use Fcntl;
use SDBM_File;

my $file = 'eijiro';
unlink "$file.sdbm.dir" if -e "$file.sdbm.dir";
unlink "$file.sdbm.pag" if -e "$file.sdbm.pag";
tie my %db, 'SDBM_File', "$file.sdbm", O_RDWR|O_CREAT, 0644 or die;
open(FP, "$file.txt") or die;
while (<FP>) {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $db{$key} = $value;
}
close(FP);
untie %db;

検索の例も載せておきます．

use Fcntl;
use SDBM_File;

my $file = 'eijiro';
tie my %db, 'SDBM_File', "$file.gdbm", O_RDONLY, 0644 or die;

my $key = $ARGV[0];
print $db{$key},"\n" if defined $db{$key};

GDBM

GNUによるDBMの実装がGDBMです．SDBMと異なりキー，バリューのサイズの制限はありません．

GDBM_File

GDBMへのPerlでのアクセスモジュールがGDBM_Fileです．基本的な使い方は， DB_Fileと同じですが，提供しているデータ形式はHASHのみです．

use Fcntl;
use GDBM_File;

my $file = 'eijiro';
unlink "$file.gdbm" if -e "$file.gdbm";
tie my %db, 'GDBM_File' , "$file.gdbm", O_RDWR|O_CREAT, 0666 or die;
open(FP, "$file.txt") or die;
while (<FP>) {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $db{$key} = $value;
}
close(FP);
untie %db;

検索プログラムを掲載します．

use Fcntl;
use GDBM_File;

my $file = 'eijiro';
tie my %db, 'GDBM_File', "$file.gdbm", O_RDONLY, 0644 or die;

my $key = $ARGV[0];
print $db{$key},"\n" if defined $db{$key};

CDB

CDBは，qmailやdjbdnsの作者であるD.J.Bernsteinが作成したデータベースで， qmailやdjbdnsのデータの保存でも実際に使用されています．非常に高速に動作しますが，キーの追加やバリューの削除などデータベースを変更することはできません(変更するなら再構築しかない)．

CDB_File

CDBへのPerlからのアクセスモジュールです．

use CDB_File;

my $file = 'eijiro';

unlink "$file.cdb" if -e "$file.cdb";
my $cdb = new CDB_File ("$file.cdb", "$file.$$") or die;
open(FP, "$file.txt") or die;
while (<FP>) {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $cdb->insert($key, $value);
}
close(FP);
$cdb->finish;

検索の方は，*DB*_Fileと同じような形になります．

use CDB_File;

my $file = 'eijiro';
tie my %db, 'CDB_File', "$file.cdb" or die "$0: can't tie to $file.cdb $!\n";

my $key = $ARGV[0];
print $db{$key},"\n" if defined $db{$key};

QDBM

QDBMは，``Quick Database Manager''という名が示すとおり，ndbmやgdbmよりも高速な実装となっているようです．またperlからは扱えませんが，全文検索用の転置インデックスを扱うAPIなども用意されています．

Depot

キーの検索にハッシュ表を用いたデータベースです．メソッドを明示的に呼び出す方法と、ハッシュにタイする方法がありますが，ここでは他のDBMSと同様に後者を用いたサンプルコードを示します．

use Depot;

my $file = 'eijiro';
unlink "$file.qdbm" if -e "$file.qdbm";
tie my %db, "Depot", "$file.qdbm", Depot::OWRITER | Depot::OCREAT;
open(FP, "$file.txt") or die;
while () {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $db{$key} = $value;
}
close(FP);
untie %db;

検索の際は

use Depot;

my $file = 'eijiro';
tie my %db, "Depot", "$file.qdbm", Depot::OREADER or die;

my $key = $ARGV[0];
print $db{$key},"\n" if defined $db{$key};

マニュアルによるとtieの引数は，tie(%hash, "Depot", $name, $omode, $bnum) となっています．$omodeはDBの接続モードの設定で代表的なものは次のものです

Depot::OWRITER	書き込みモード
Depot::OREADER	読み込み専用モード
Depot::OWRITER \| Depot::OCREAT	DBがない時は作成する
Depot::OTRUNC	DBが既にあっても新規に作成

$bnumはバケットサイズでハッシュ表のサイズを設定します．格納されるすべてのデータ数の0.5～4倍ぐらいが推奨されています．

Curia

基本的にはDepotと同じですが，単独のファイルにデータを保存するのではなく，複数のファイルに分割して保存するために大量のデータを扱うのに適しています．書式はDepotと同じなのでサンプルコードは略．

Villa

キーの格納に木構造の1つであるB+木を使用しています．DB_TREEと同様に重複したキーを扱えたり，キーの辞書順にデータを取り出したりすることができます．ここでは辞書の前方一致検索を行なうコードを示します．

use Villa;

my $file = 'eijiro';
unlink "$file.qdbm.villa" if -e "$file.qdbm.villa";
my $villa = new Villa("$file.qdbm.villa", Villa::OWRITER | Villa::OCREAT) or die;

open(FP, "$file.txt") or die;
while () {
    chomp;
    my ($key, $value) = split(/:/, $_, 2);
    $villa->put($key, $value, Villa::DDUP);  # 重複を許す
}
close(FP);
$villa->close();

Villaでは，カーソルを用いた順序に基づくキーの走査が可能になります．

use Villa;

my $file = 'eijiro';
my $villa = new Villa("$file.qdbm.villa", Villa::OREADER) or die;

my $prefix = $ARGV[0];

$villa->curjump($prefix);             # カーソルを候補の先頭に置く

while ( my $key = $villa->curkey() ){ # カーソルが現在指しているキーを取得
    if ( $key =~ /^$prefix/ ) {       # 前方一致
	my $val = $villa->curval();
	print "$key\t$val\n";
	$villa->curnext();            # 次のカーソルへ
    } else {
	last;
    }
}
$villa->close();

TDB

TDB_File

TODO

SQLight

DBD::SQLight

TODO

Suffix Array

今までのデータベースとは全く異なったもので，Suffix Arrayというデータ構造を用いてテキストファイルの全文検索を可能にしたものです．本来は1つのファイルに複数記事があるとき，検索語を含む記事を検索するなどの用途に使用するのですが，今回は辞書検索に使用してみます．

SUFARY

mkaryというプログラムを用いてインデックスであるarrayファイルを作成します．オプション無しで作成テキストファイル内のすべての部分文字列を検索するarrayファイルができますが，今回は辞書形式のファイルなので``-l''オプションをつけ，行頭からのみ検索できるようにします．

mkary -l eijiro.txt

すると``eijiro.txt.ary''というarrayファイルが作成されます．簡単な検索プログラムは，以下の通りです．このままではフレーズを含め検索語から始まる行がすべてヒットしてしまうので，キーが検索語と一致する行のみを出力させています．

use SUFARY;

my $file = 'eijiro';
$x = SUFARY->new("$file.txt") or die $!;

my $key = $ARGV[0];
if ( $x->search($key) ) {
    my $all_line = $x->get_all_line;
    foreach my $line ( @$all_line ) {
	my ($k,$v) = split(/:/,$line,2);
	print "$v\n" if $k eq $key;
    }
}

詳しい使い方は，SUFARYのマニュアルを御覧下さい．

SARY

SUFARYをC++で実装し，インターフェースをオブジェクト指向風にしたものが SARYです．基本的な使い方は同じですし，作成されるarrayファイルもSUFARY と同一です．arrayファイルの作成方法は，

mksary -l eijiro.txt

となり，簡単な検索プログラムは，

use Search::Saryer;

my $file = 'eijiro';
my $saryer = Search::Saryer::new(filename=>"$file.txt") or die $!;

my $key = $ARGV[0];
if ( defined $saryer->search($key) ) {
    while ( defined ($line = $saryer->get_next_line()) ) {
	my ($k,$v) = split(/:/,$line,2);
	print $v if $k eq $key;
    }
}

となります．

複雑なデータ構造

今までは，``$hash{$key}=$value''のように 1つのエントリーが単純な組の場合を扱ってきました．Perlの連想配列では ``$hash{$key1}{$key2}''のような配列の配列といったデータ構造を持つことができますが，前述のデータベースではこのような複雑な構造を扱うことが出来ません．ここでは複雑なデータ構造を扱うモジュールを紹介します．

Data::Dumper

Data::Dumperは複雑な連想配列の中身を表示したり，テキストに保存するために使用されます．使い方の例は，

use Data::Dumper;

my @colors = qw(red blue green);
my @fluits = qw(orange banana apple);
my %hash;
foreach my $c ( @colors ) {
    foreach my $f ( @fluits ) {
	$hash{$c}{$f} = 1;        # 連想配列を作成
    }
}

open(FP,'> dump.txt') or die;     # 保存するファイルを開く
print FP Dumper(\%hash);          # 連想配列の内容をファイルに書き出す
close(FP);

そうすると``dump.txt''は次のようになります．

$VAR1 = {
          'green' => {
                       'banana' => 1,
                       'apple' => 1,
                       'orange' => 1
                     },
          'blue' => {
                      'banana' => 1,
                      'apple' => 1,
                      'orange' => 1
                    },
          'red' => {
                     'banana' => 1,
                     'apple' => 1,
                     'orange' => 1
                   }
        };

実は，これはPerlスクリプトの書式に則っていますので，別のスクリプトから読み込むことにより連想配列を再現することが出来ます．

use Data::Dumper;

my $hash_ref = require 'dump.txt';

foreach my $c ( keys %{$hash_ref} ) {
    foreach my $f ( keys %{$hash_ref->{$c}} ) {
	print "$c\t$f\n";
    }
}

Storable

Data::Dumperと同様，複雑なデータ構造をもつ変数をファイルへ保存しますが，メモリで記憶しているそのままの形式で保存するので，保存されたファイルの中身を見ても意味はないですが，書き出しや読み込みは高速化されています．

use Storable qw(store);

my @colors = qw(red blue green);
my @fluits = qw(orange banana apple);
my %hash;
foreach my $c ( @colors ) {
    foreach my $f ( @fluits ) {
	$hash{$c}{$f} = 1;
    }
}
store(\%hash, 'store.bin') or die;

このとき保存されたファイルとData::Dumperで保存したファイルのサイズは次のようになります．

dump.txt  482
store.bin 167

読み込みは，次のようになります．

use Storable qw(retrieve);

my $hash_ref = retrieve('store.bin');

foreach my $c ( keys %{$hash_ref} ) {
    foreach my $f ( keys %{$hash_ref->{$c}} ) {
	print "$c\t$f\n";
    }
}

MLDBM

最後に，いままで紹介した各DBMを複雑なデータ構造が保存できるように拡張したものが，MLDBMです．連想配列の中のリファレンスを1つの文字列にシリアライズすることによってデータをDBMに格納します．

MLDBMでは，DBMにBerkeleyDB, DB_File, SDBM_File, GDBM_Fileを，シリアライザにはData::Dumper, Storable, FreezeThawの各モジュールを使用することが出来ます(デフォルトはSDBM_FileとData::Dumper)．ただ，SDBM_Fileはサイズの制限があるので代わりにDB_Fileなどを，速度の面からData::Dumper よりはStorableを使うことをお薦めします．

use Fcntl;
use MLDBM qw(DB_File Storable);      # ここで使用するモジュールを指定

my @colors = qw(red blue green);
my @fluits = qw(orange banana apple);
unlink "mldbm.db" if -e "mldbm.db";

tie my %hash, 'MLDBM', 'mldbm.db', O_RDWR|O_CREAT, 0644, or die;
foreach my $c ( @colors ) {
    foreach my $f ( @fluits ) {
	$hash{$c}{$f} = 1;
    }
}

MLDBMに関連づけられた連想配列の値を変更するとき，1つ注意点があります．

$mldb{key}{subkey}[3] = 'stuff';    # 動かない

代わりに以下のように書きます

$tmp = $mldb{key};                  # 値の取り出し
$tmp->{subkey}[3] = 'stuff';
$mldb{key} = $tmp;                  # 値の格納

いろいろな比較

TODO

Link

Berkeley DB (http://www.sleepycat.com/)
CDB (http://cr.yp.to/cdb.html)
QDBM (http://qdbm.sourceforge.net/)
SUFARY (http://nais.to/~yto/tools/sufary/)
SARY (http://sary.namazu.org/)

サンプルデータについて

英辞郎

速度の比較をするために，割と大きいテキストファイルを探していたのですが，誰でも入手できるものってなかなか存在しないものですね．そこで英辞郎を使用することにしました．今回は書籍で販売されている英辞郎の第4刷のCD-ROMに収録されているEIJIRO52.TXTを使用しています．

以下のスクリプトを用いて，特に必要なさそうなデータを削除します．

#!/usr/bin/perl
# 英辞郎の辞書ファイルからデータをいくつか削除
while ( <> ) {
    s/^■//;
    s/\{.+?\}//g;
    my ($entry, $meaning) = split(/:/,$_,2);
    $meaning =~ s/^\s+//;
    next if $meaning =~ /^【/;
    $meaning =~ s/｛.+?｝//g;
    $entry =~ s/\s+$//;
    print $entry, ':', $meaning;
}

これにより辞書ファイルは，1055725行，45,280Kbのファイルになります．これをeijiro.txtとします．各行のフォーマットは「見出し:説明\n」となっています．

Up(P): Home

間違え，勘違い，スペルミスなどは mail まで

Last modified: Sat Mar 26 01:36:25 JST 2005

perlによる大規模データの取扱い

Menu

BerkeleyDB

DB_FIle

GDBM_File

CDB_File

Depot

Curia

Villa

TDB_File

DBD::SQLight

SUFARY

SARY

Data::Dumper

Storable

MLDBM

いろいろな比較

英辞郎