転置インデックス[2007-06-17-6]による検索システムの実装は
パフォーマンスを無視すれば意外と簡単です。
それを示すために Perl で簡単な検索システムを作ってみました。
検索方式は転置インデックス(Inverted Index)、
ランキングには TF-IDF[2005-10-12-1] を用いました。

検索対象ファイルは一行一記事で以下のフォーマットとします。

[記事ID][SPC][記事内容]\n

記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。
以下のようなサンプル test.txt を用意しました。

1 これはペンです
2 最近はどうですか？
3 ペンギン大好き
4 こんにちは。いかがおすごしですか？
5 ここ最近疲れ気味
6 ペンキ塗りたてで気味が悪いです

まずは、インデックスを作ります。
インデックス単位は文字bigram (隣接2文字)とします。
インデックスファイルのフォーマットは以下の通りです。

[文字bigram][SPC][出現記事ID,出現記事ID,...]\n

検索対象ファイルからインデックスファイルを作成するプログラム
index.pl です。

 1  #!/usr/bin/perl
 2  use strict;
 3  use warnings;
 4  my $num;
 5  my %idx;
 6  while (<>) {
 7      next unless (/^(\d+) (.+)$/);
 8      my ($id, $c) = ($1, $2);
 9      my @char = ($c =~ /([\x00-\x7f]|[\xC0-\xDF][\x80-\xBF]|
10                    [\xE0-\xEF][\x80-\xBF]{2}|
11                    [\xF0-\xF7][\x80-\xBF]{3})/gsx);
12      my %seen;
13      for (my $i = 0; $i < $#char; $i++) {
14          my $bigram = join("", @char[$i, $i+1]);
15          next if exists $seen{$bigram};
16          push @{$idx{$bigram}}, $id;
17          $seen{$bigram} = 1;
18      }
19      $num++;
20  }
21  print "\#NUM=$num\n";
22  foreach (sort keys %idx) {
23      print "$_ ".join(",", @{$idx{$_}})."\n";
24  }

6-20行が検索対象ファイルを読み込みインデックスを作成する部分、
21行以降が作成したインデックスを出力する部分です。
前者では、一行ずつ読み込んだ記事の記事内容文字列を
文字に分解し(9-11行)、
隣接する2文字をつなげてbigramにし(14行目)、
そのbigramが出現する記事IDをハッシュに格納しています(16行目)。

これを実行してインデックスファイル test.idx を作ります。

% ./index.pl test.txt > test.idx

完成したインデックスファイル test.idx は以下のようになります
（長いので途中部分を省略しています）。
NUMは検索対象ファイルに含まれている記事数で、
TF-IDFのIDFの計算に使用します。

#NUM=6
。い 4
いか 4
いで 6
うで 2
おす 4
か？ 2,4
...
悪い 6
最近 2,5
気味 5,6
疲れ 5
近は 2
近疲 5

さて、次はこのインデックスファイルを使って検索します。
検索プログラム search.pl は以下の通りです。

 1  #!/usr/bin/perl
 2  use strict;
 3  use warnings;
 4  my $num;
 5  my %idx;
 6  open(F, shift @ARGV) or die;
 7  while (<F>) {
 8      if (/^\#NUM=(\d+)/) {
 9          $num = $1;
10      } elsif (/^(\S+) (.+)$/) {
11          @{$idx{$1}} = split(",", $2);
12      }
13  }
14  close F;
15
16  while (<>) {
17      my %score;
18      my %tf;
19      my @char = (/([\x00-\x7f]|[\xC0-\xDF][\x80-\xBF]|
20                    [\xE0-\xEF][\x80-\xBF]{2}|
21                    [\xF0-\xF7][\x80-\xBF]{3})/gsx);
22      for (my $i = 0; $i < $#char; $i++) {
23          $tf{join("", @char[$i, $i+1])}++;
24      }
25      foreach (keys %tf) {
26          my $df = (exists $idx{$_}) ? @{$idx{$_}} : 0;
27          my $idf = log($num / ($df + 1));
28          my $tfidf = $tf{$_} * $idf;
29          foreach (@{$idx{$_}}) {
30              $score{$_} += $tfidf;
31          }
32      }
33      print;
34      foreach (sort {$score{$b} <=> $score{$a}} keys %score) {
35          print "ID:$_ SCORE:$score{$_}\n";
36      }
37  }

6-14行が先ほど作ったインデックスファイルを読み込む部分、
19-24行が検索キー文字列をbigramにしそれぞれのTFを計算する部分、
25-32行が各bigramごとにTF-IDFを計算し各記事のスコアに加算する部分、
33行以降が各記事をスコアの高い順に出力（検索結果ランキング表示）
する部分です。

では search.pl で検索してみます。
第一引数にインデックスファイルを指定します。
検索キーは標準入力から入力します。文字コードは UTF-8 です。

% echo '最近ペンギンが好きです'|./search.pl test.idx
最近ペンギンが好きです
ID:3 SCORE:3.70130197411249
ID:2 SCORE:0.8754687373539
ID:5 SCORE:0.693147180559945
ID:6 SCORE:0.587786664902119
ID:1 SCORE:0.587786664902119
ID:4 SCORE:0.182321556793955

一番スコアが高いのが記事ID 3の「ペンギン大好き」でした。

なお、この実装では極端に長い記事のスコアが高くなる傾向にあり、
検索精度が問題になると思われます。
スコアを長さで正規化すると良いかもしれません。

Google や Yahoo! などの Web 検索エンジンも、
Namazu や Hyper Estraier などの全文検索エンジンも、
基本はこれです。