昔、全文検索エンジンを作っていた

これは単なる昔話である。

しかし、ある種の人達にとっては、「技術的昔話」はとても意味のあることもある。それは技術そのものではない事情だ。そういった人達のために記録しておく。この文章の技術的な価値は、現代ではほぼ0であろう。以下の話は技術的なことに見えるが、あくまでもそれは

エビデンス

としてであって、技術そのものとしては価値はない。今となっては、誰でも知ってることに過ぎない。「当時」だから価値があったのだ。願わくは、この文章が価値を持たないで欲しいと思いつつ書いている。

太古の昔、まだパソコンが16bit CPUを使い始めた頃、MS-DOS Ver 3.0なんてのを使い、メモリは1MBもあれば贅沢だった時代、Cコンパイラが10万くらいした時代、私はその頃にCを覚えた。今からざっと30年近く前である。そして、初めて書いたプログラムがある種の全文検索エンジンだった。

「全文検索エンジン」と言ってしまったが、その当時、そういった概念は多分なかった(少なくとも当時の私は見たことも聞いたこともない)。その頃にあった「情報検索」は、文献タイトルやシソーラスから転置ファイルを作り、

タグ検索や前方一致検索

を駆使して、「サーチャー」なんて人がオペレーションをしていたものだった。今の「検索エンジン」みたいな簡単なものじゃなかったのだ。

そんな時、どんな経緯だったかよく覚えてないが、当時富士通系のSE会社にいた私は、

文献検索のパッケージ

を作ることになった。BASICでプロトタイプを作ってみたら思いの外高速だったので、いけるんじゃね? と思って社内提案したということは覚えている。もっとも、その時は

インデクスを全く作らないでメモリ上で検索する

というものだった。当時のパソコンの容量のことを考えれば、これでも十分な速度だったのだ。何しろ、そんなに大量のデータが記憶出来ないんだから。

それからしばらく他の仕事で忙殺されていて、実際に着手したのはもっと後だったと思う。そして、それを作るという口実でC(Lattice-C)を買ってもらった。Cの勉強はそれから本格的にやったw

まずはUIのためのライブラリとか実装していたのだが、その辺のことは割愛する。

せっかくCで書くのだから、商用の情報検索システム(当時はそう呼んでいた)と同じような機能を載せようと、いろいろ考えていたのだが、ある時ふと

どうせシソーラスまとめるんだったら、それで辞書テーブル作って、さらにそれを転置ファイルにしたら良いんじゃね?

ということを思いついた。そうすれば、「シソーラス」を作る(まとめておく)ことと、検索のためのテーブルを作ることが一致する。

そうやって文献情報を格納するテーブルを考え始める。当時は今で言うところの「タグ(キーワード)」のようなものを文献のエントリに付与してやって、それを元に検索するのが普通だった。当時のシソーラスはその辺に顔を出して来るのだが、そのうち

シソーラスは、文献(の概要)の中に現れる単語の部分集合である

ことに気がつく。そうすると、何もわざわざシソーラスでタグを作るなんて面倒なことをしないで、

文献(の概要)をparseする

ことで自動的にタグがついたのと同じようなことが出来ることに気がついた。

「タグ」はいくつでもつけられると便利だ。ところが、そういった「いくつでも」というのは、当時のパソコンと当時の私の技術では「やれないことはないけど面倒臭い」ことだった。何しろ、つい先日Cを覚えたばかりでもあったし。でも、「文献(の概要)」だけであれば、可変長にしてもそんなに面倒な思いをすることもないし、parseするコストが十分低ければ、たいした問題じゃない。それに、インデクスは一度張ってしまえばそれでいいわけなんで、parseのコストが問題になるのは登録時だけだ。

で、文章をparseすることを考えなきゃいけないのだが、当時は今のようにお手軽な形態素解析ライブラリなぞ存在していない。ではどうするかと言えば、

シソーラス辞書をhashにする

ことで、parse用の辞書と兼用する。発見したいのは文献(の概要)の中にあるシソーラスに一致した単語(ほとんどが名詞)であるので、辞書はこれで十分だ。解析処理は、

文献(の概要)の頭から辞書にある一番長い単語長から1文字づつ減らしながら切り出し、辞書のhashに当たる

ことで行うようにした。hashの実体はファイル上にあったが、それでも十分高速だった。

不要語とか格変化とかのような言語処理の部分は端折った。てか、そこで下手に言語処理をすると、多言語化の時に問題になる。まぁ、当時は日本語と英語しかなかったんだけど。

そういった手抜きをすると、当然ながら不要語とか格変化とかあたりのことがノイズの元になるのだが、

検索文字列のparseも同じことをする

ことで、同じようなノイズが入るようにした。そうすれば、ノイズの存在がいい感じに隠蔽される。

インデクスであるが、これはいわゆるB-treeの類ではなくて、シソーラス辞書にぶら下がるpointer arrayにした。この方が実装は簡単だし(当時はB-treeは自分で実装しなきゃいけないものだった)、メモリ節約出来るし、必要にして十分だった。

pointer長をどうするか、pointer arrayが可変長になるという面倒臭さをどうするかしばらく悩んだのだが、当時のパソコンの容量とかとのバランスも考えて、

bitmap index

にすることを思いついた。「n番目のポイント」を表現するために「n番目のbitを立てる」という方法である。もちろんそんなものは当時の私に見える文献にはないのだけど、容量とpointer長のバランスを

32bit(4byte)では無駄に長過ぎるし、
16bit(2byte)だと短いかも知れない

とか考えていて(メモリが512kB、ディスクが40MBくらいの時代である)、

bitmapなら長さに悩まなくていーじゃん
それにどうせsparseだろうし

ということに気がついた。さらに都合の良いことは、文献の集合演算がbitmapの論理演算に帰着出来る。

もちろんbitmapそのままで保存すると大きくなり過ぎるので、bitmapをブロックに分け、空のブロックは記録しないという工夫もした。そうすると、空のブロックは論理演算から外すことが出来るので、さらに都合がいい。

当時の「情報検索」では検索結果の件数を表示することは重要だったのだが、そのためには「立っているbit」の数を数えるだけでいい。

というようにすると、文献検索をするのにインデクス、それもごく小さいデータのハンドリングだけで、目的の情報に到達出来る。まさに今の「検索エンジン」と同じことが出来る。当時の「情報検索」は何らかの形で「文献データ」を読んでgrepのような処理をしていたのだが、その辺の処理を全く省くことが出来た。お陰で、当時は

どんなトリックを使った?

と言われるくらいだった。何しろデータにも検索文字列にも、普通の文章が入れられているだけなのだ。それで一瞬(フロッピーでやっても数秒)で検索結果が出るのだから、当時としては

魔法

みたいに見えて当然だ。今はどうってことのない日常だけどね。

当時は1本8万円くらいで売ってたと思う。ターゲットマシンがFM-16βなんつーマイナー機でもあったし、そんなに宣伝したわけでも力を入れて売ってたわけでもないので、たいして売れた覚えはないのだけど、コンパイラ代やパンフレット代くらいにはなったと思う。

全文検索をいつ誰が発明したかは知らないが、少なくとも当時の私はそれとは別に発見していた。

Yahoo Facebook Twitter Digg FriendFeed Delicious Google Translate
This entry was posted on10月 13th, 2015 at 13:21:10. You can follow any responses to this entry through the RSS 2.0. Responses are currently closed, but you can Trackback..

Comments are closed.

  • 私について

    ただのプログラマです、ハッカーではありません。

    秋葉で暮し秋葉で仕事してますが、秋葉系は嫌いです。物事を冷静に分析することは好きですが、ニヒリストは嫌いです。

    秋葉でちっこい会社をやってます。 こーゆーことがお仕事です。

    詳しいことは、自己紹介のページでも見て下さい。また、mixiの方でもいろいろわかるかも知れません。twitterは@ogochanですが、たいしたこと言ってません。近頃はShorplug内の別館で日記書いたりもしてます。だいたいここのコピーだったりしますが、ログインするとコメントがつけられます。

    日経ITProに連載(生越昌己のオープンソースGTD)を書いています。「ちゃんと書いた文章」が読みたい人は、そっちを読む方がいいと思います。

  • このページについて

    ここは私の雑文の置き場です。WordPressを使っていますが、いわゆるblogのつもりで書いているわけではありません。「覗き見のできるチラ裏」くらいの意味しかありません。

    もしかしたら有用なことがあるかも知れません。あるいはむかつくことも書いてあるかもしれません。それらはみな「そんなものだ」と思っておくに留めましょう。

    コメントを書くのは構いませんが、「反論」の類はよそでやって下さい。同意する気のない人達と議論する気は全くありませんので、議論したければよそで勝手にやって下さい。

    と言っても、「読むな」「広めるな」というわけでもありません。リンク、ブクマの類は御自由に。

  • カテゴリ

  • 過去の記事

  • メタ情報