たつをの ChangeLog : 2007-11-26

毎月一本公開の「タビデオ」(Tavideo)、第三回の11月号です。
だいぶ慣れてきました。
まず前の月のデータをコピーしてから作り始めるので、かなり作業が楽に。

月刊 タビデオ ２００７年１１月号 (YouTube)


■内容：
(1) カンパイ（恵比寿）
(2) ソバパスタ
(3) ブックオフ（中目黒）
(4) Rolly（五反田）
(5) インドのお香
(6) ボジョレーヌーボー（代々木）
(7) みなとみらい（横浜）
(8) 恵比寿麦酒記念館（恵比寿）
(9) コーヒーをいれる
(10) 中目黒（中目黒）

■情報：
- 撮影機材：Xacti
- 編集機材：MacBook (黒)
- 撮影場所：恵比寿、中目黒、五反田、横浜、代々木、etc.
- 編集場所：自宅
- 撮影・編集：たつを

§

前回の予告どおり[2007-10-28-1]、
今回は何箇所かで100円ショップで買ったホワイトボードを
使ってみました。
手作り度がよりアップして良い感じになったかな？どうかな？

まつげ育毛剤入りというのがあるらしい。女性に人気らしい。
で、思いついたんだけど、目薬にまつげ育毛剤が入ってたらよくない？
目からあふれた目薬がまつげの根本に浸透するわけです。
まあ、目にやさしい育毛剤ってのがあるかどうかがすべてですが。

■唐沢俊一 / トンデモ一行知識の世界


まえがきで紹介されていたアイザック・アシモフの言葉：

人間は、無用な知識の数が増えることで快感を感じることができる、
唯一の動物である

アシモフの雑学本[2004-03-02-3]はお薦めですよ。

真偽はともかく、この本で紹介されていた一行知識をいくつかピックアップ。

統計によると、騒がしい人ほどよく本を読む。

本をよく読む人はその内容を語りたがる率が高いのかも。
騒がしい人がよく本を読む、とは言い切れないけど、
よく本を読む人のなかに語りたがりで騒がしい人が多いかも。
そうでもないかも。

ラムネのビンの中には栓用のガラス玉が入っているが、
その玉の規格品はA、不良品はBと分類され、
不良品は子供のオモチャに下取りされた。
これがビー玉の語源となった。

いかにもインチキトリビアっぽい感じが面白い。

『はじめての一太郎』などの解説書を出している秀和トレーニング。
C言語の解説書はもちろん『はじめてのC』

当時は恥ずかしくて買えなかった。
で、別の出版社のを買った。

「働きバチのように働く」というが、
働きバチの働いている時間の総計は一日五時間にすぎない。

一部の「忙しい、忙しい」と言っている人の総労働時間は、うんぬん。

ハンバーガーはドイツのハンブルグ市に由来する名前だが、
チーズバーガーはチーズブルグ市（実在する）には何の関係もない。

ハンバーガー以外の「○○バーガー」って言い方がそもそもねえ。

- あなたが一番好きなアルゴリズムを教えてください。
  また、その理由やどんな点が好きなのかも教えてください。
  http://q.hatena.ne.jp/1195950564

やはり、Suffix Arrays ですね。
あのシンプルさと汎用性は尋常じゃない。
出会ってから今まで使い慣れたツールとして活用しまくってます。
たいていの用途にはそこそこの性能で使えて便利。
どうしてもダメなときは他の方法に切り替えますけどね。

って、アルゴリズムじゃなくてデータ構造か、これは。

ref.
- [を] Suffix Array の解説文書のリンク集[2006-04-10-3]
- [を] SUFARY のパッケージに付属のドキュメント[2006-04-25-2]
- [を] Perl による Suffix Array の実装[2006-04-10-2]
- 404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたい
  アルゴリズムx10
  http://blog.livedoor.jp/dankogai/archives/50957658.html

転置インデックス[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 などの全文検索エンジンも、
基本はこれです。