古い記事
ランダムジャンプ
新しい記事
「Introduction to Information Retrieval」[1]の第四章[2008-04-12-2]の「4.5 Dynamic indexing 」に出てくる Logarithmic Merging のアルゴリズム (Figure 4.7) を説明用に Perl で実装してみました。
といっても、説明用プログラムなので、実際とは異なります。
実際は postings のマージをやるんだけど、term のマージだけ。
indexes と Z と I がどのように変化するのかを追って処理の流れを確認するためだけのものです。

コード:
#!/usr/bin/perl
use strict;
use warnings;

my $cnt = 1;
sub GetNextToken { # uniq vocab. 本当は vocab+posting.
    return $cnt++;
}

# Logarithmic Merge
my @Z;
my @I;
my %indexes;
my $n = 2; # num of vocab. 本当は num of postings.
for (my $i = 0; $i < 100; $i++) {
    print "step ".($i+1)."\n";
    LMergeAddToken(GetNextToken());
}

sub LMergeAddToken {
    my ($token) = @_;
    @{$Z[0]} = Merge(@{$Z[0]}, $token);
    if (@{$Z[0]} == $n) {
	for (my $i = 0; $i < 100000000; $i++) {
	    if (exists $indexes{$i}) {
		@{$Z[$i+1]} = Merge(@{$I[$i]}, @{$Z[$i]});
		delete $indexes{$i};
	    } else {
		@{$I[$i]} = @{$Z[$i]};
		$indexes{$i} = 1;
		print_info();
		last;
	    }
	    print_info();
	}
	@{$Z[0]} = ();
    } else {
	print_info();
    }
}

sub Merge { # 本当は postings をマージする。
    return @_;
}

sub print_info {
    print " indexes: ", join(",", keys %indexes), "\n";
    for (my $i = 0; $i < @Z; $i++) {
	print " Z_$i: ", join(",", @{$Z[$i]}), "\n";
    }
    for (my $i = 0; $i < @I; $i++) {
	print " I_$i: ", join(",", @{$I[$i]}), "\n";
    }
}

実行結果:
step 1
 indexes: 
 Z_0: 1
step 2
 indexes: 0
 Z_0: 1,2
 I_0: 1,2
step 3
 indexes: 0
 Z_0: 3
 I_0: 1,2
step 4
 indexes: 
 Z_0: 3,4
 Z_1: 1,2,3,4
 I_0: 1,2
 indexes: 1
 Z_0: 3,4
 Z_1: 1,2,3,4
 I_0: 1,2
 I_1: 1,2,3,4
step 5
 indexes: 1
 Z_0: 5
 Z_1: 1,2,3,4
 I_0: 1,2
 I_1: 1,2,3,4
step 6
 indexes: 1,0
 Z_0: 5,6
 Z_1: 1,2,3,4
 I_0: 5,6
 I_1: 1,2,3,4
step 7
 indexes: 1,0
 Z_0: 7
 Z_1: 1,2,3,4
 I_0: 5,6
 I_1: 1,2,3,4
step 8
 indexes: 1
 Z_0: 7,8
 Z_1: 5,6,7,8
 I_0: 5,6
 I_1: 1,2,3,4
 indexes: 
 Z_0: 7,8
 Z_1: 5,6,7,8
 Z_2: 1,2,3,4,5,6,7,8
 I_0: 5,6
 I_1: 1,2,3,4
 indexes: 2
 Z_0: 7,8
 Z_1: 5,6,7,8
 Z_2: 1,2,3,4,5,6,7,8
 I_0: 5,6
 I_1: 1,2,3,4
 I_2: 1,2,3,4,5,6,7,8
step 9
 indexes: 2
 Z_0: 9
 Z_1: 5,6,7,8
 Z_2: 1,2,3,4,5,6,7,8
 I_0: 5,6
 I_1: 1,2,3,4
 I_2: 1,2,3,4,5,6,7,8
step 10
 indexes: 0,2
 Z_0: 9,10
 Z_1: 5,6,7,8
 Z_2: 1,2,3,4,5,6,7,8
 I_0: 9,10
 I_1: 1,2,3,4
 I_2: 1,2,3,4,5,6,7,8
step 11
 indexes: 0,2
 Z_0: 11
 Z_1: 5,6,7,8
 Z_2: 1,2,3,4,5,6,7,8
 I_0: 9,10
 I_1: 1,2,3,4
 I_2: 1,2,3,4,5,6,7,8
...

参考文献:
[1] Christopher D. Manning, Prabhakar Raghavan and Hinrich Schu"tze:
  Introduction to Information Retrieval, Cambridge University Press, 2008.
  (http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html)
この記事に言及しているこのブログ内の記事