たつをの ChangeLog : 2008-04-12

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

「Introduction to Information Retrieval」の輪講の第五回を開催しました。

- Introduction to Information Retrieval
http://www-csli.stanford.edu/~hinrich/information-retrieval-book.html

場所は大岡山の東工大でした。ありがとうございました。
電源が充実で「電源充」でした。


今回は第４章「Index construction」でした。

内容メモ：
- term と termID のマッピング (ref. [2008-04-10-2])
- BSBI と SPIMI
- MapReduce (ref. [2008-03-25-1])
- Logarithmic Merging (ref. [2008-04-12-1])

追記080512:
- MapReduce - naoyaのはてなダイアリー
  http://d.hatena.ne.jp/naoya/20080511/1210506301