第2回飛行機の中で

前回は、FINDSPOTの開発を行うきっかけとなった問題意識の芽生えについて紹介しました。今回は、開発のきっかけや初期のコードがどのように進化していったのかについて紹介しましょう。

最初のコードは365行

2003年の6月にアメリカから出張帰りの飛行機の中で、ふと、アルゴリズムの勉強がてらUnicode(UTF-16)をベースにしたN-gram(エヌグラム)のインデックスによる検索のサンプルコードを書いてみようと思い立ちました。N-gramとは、N文字分の文字の連なりをキーとしてインデックスを作成する全文検索の古典的な手法です。

形態素解析による分かち書きでは、辞書にない語がうまく処理できない限界や、他言語への対応が難しいという問題があります。N-gramでは文字の連なりがインデックスのキーとなるので、形態素解析の分かち書きで作られた文字列キーよりもキーの数が大きくなります。しかしハードウェアの進化により、N-gramによる実用的な検索エンジンの実現はすでに可能な時期になっているのではないかと直感したのです。N-gramによる検索では、形態素解析を行わないため、形態素解析用の辞書のメンテナンスが不要です。また、Unicodeをベースにしたインデックスにすれば、懸案の多言語に対応した検索エンジンが実現できます。

今でもその時のコードが残っています。わずか365行のC++のソースコードと、75行のSQL文です。PostgreSQLのテーブルを使って、検索対象の文書の書誌情報と、インデックスを管理するものでした。サンフランシスコから成田に着くまでの間にPowerBookを使って書いた、このサンプルコードは立派に機能してくれました。

N-gramのアルゴリズムが動くことは確認できたものの、飛行機の中で書いたコードはインデックス作成スピード、検索実行スピードのいずれをとっても遅すぎました。実用的な検索エンジンと比べると、F1レーシングカーとありんこ位の差があります。しかし乗りかかった舟ということで、このコードを出発点にどこまで検索エンジンの形に仕上げられるかやってみようと思い立ったのです。これからひたすら検索エンジンの性能や機能との戦いが始まりました。

深夜のスターバックスにて

とはいっても、別段、検索エンジンを開発する仕事を請け負っていたり、補助金などの助成を受けていたわけでもありません。検索エンジンのプログラム開発は本業の仕事が終わってからということになります。近所にできたばかりのスターバックスコーヒーに夜中の2時ごろまで居座ったりして、徐々にコードが大きくなっていきました。開発は直接の仕事ではないので締め切りもなく、気軽に臨めたのが良かったのでしょう。一つ問題をクリアすると新たな課題が見つかるのですが、あまりプレッシャーなども感じないで淡々と開発が進行していくような状況でした。

7月に入り最初に手をつけたのが、SQLのデータベース部分です。最初の実証用コードではデータベースとしてPostgreSQLを使っていましたが、この部分をそっくりMySQLに変更したらどうだろうと考えたのです。残念ながら結果は若干のスピードアップだけでした。当初、SQLのデータベースはN-gramのインデックス保存や検索用に使用しても十分に速いのではないかと勝手に予測していたのですが、実際にスピードを計測してみると、まったく使い物にならないということが明らかになりました。

この時のコードで、大きな変化がもう一つあります。FINDSPOTという検索エンジンの名称を使い始めたのです。FINDSPOTは次のような意味を持つ英単語です。

検索エンジンの開発を始めてから、ちょうど良い名前がないかとずっと思い巡らしていたのですが、相変わらず夜中のスタバで、何の気無しに英語の辞書を検索していたところ、findspotという単語を見つけました。findspotという単語が、辞書データの中から掘り出されたような印象で、これはコンセプトとしてぴったりだなと思ったものです。

7月の半ばにさしかかったころに、N-gramのインデックスを格納する独自のインデックスファイルを設計し、高速にインデックスを格納・検索できるように改良しました。N-gramのインデックスの検索が終わると、ヒットした文書IDの一覧が得られる内部構造になっているのですが、文書IDから、文書のファイル名、日付、サイズなどのプロパティ情報を取得する部分はMySQLのテーブルを使って実現しました。独自形式でインデックス情報を扱い、汎用的なSQLデータベースで書誌情報を別々管理する構造は現在でも維持しているFINDSPOTの基本構造です。

このコードはかなりの検索スピードを備えており、FINDSPOTはきっと使い物になるゾと予感したものです。しかし、検索エンジンでは必須機能である条件検索や、検索結果の表示順の制御がまだ備わっていませんでした。車でいえば、車台にエンジン、タイヤ、ハンドルが付いただけの状態です。

その後は、ひたすら検索エンジンとしての完成度を上げる努力を続け、AND, OR, NOTなどの条件検索や、検索結果の表示順の制御の他、PerlによるCGIのインターフェース、Mac OS X, FreeBSD, LinuxなどのUNIXだけでなくWindowsへの対応を行いました。コンパクトな検索エンジンとしての体裁が整って開発が一段落したのは2003年の9月半ばになっていました。