前の記事 / 次の記事 / トップ

「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)

この記事に言及しているこのブログ内の記事
一言メッセージ送信: 私宛の一言メッセージをこっそり送信できます(非公開)