この記事は日経バイトの「技術の真髄」という連載向けに書きまし た。連載の内容は 「ソフトウェアの匠」 という書籍にまとめられ、本記事も収録されています。
はじめに
数年前まではよく耳にしたが最近ではあまり聞かなくなった話題と いうものがある。情報の氾濫が深刻化して必要な情報を見つけ出せ なくなる云々、というのもそのひとつだ。実際に深刻化が収まって きたのか、単にニュースとして取り上げられなくなっただけなのか 不明だが、近年、インターネット上の検索技術は情報の急激な増加 に追いつくべく格段に向上している。
現在ネット検索の代名詞になっているGoogle社は、ミッションと して「世界中の情報を組織化し、世界中のユーザがその情報を利用 できるようにすること」をかかげている。Googleだけが検索エン ジンではないが、ネット上の情報へのアクセスが大幅に改善された のは同社の取り組みに負うところが大きい。
情報へのアクセスがしやすくなったことから、旧来なら手間がかか りすぎてアクセスできる人が限られていたような情報も、現在では その多くがネットで検索して簡単に手に入れられるようになった。 この結果、ITを使える人と使えない人の情報格差 (デジタルデバイ ド) が広まる一方で、一般人と専門家の間で情報収集の手段に差異 がなくなり、両者の情報格差が狭まるという現象も同時に進行して いる。
こういった流れの中で、筆者が興味を持って取り組んできたのは、 (Google風に言うと) 「自分の情報を組織化し、自分がその情報 を利用できるようにすること」という実に自己中心的なテーマであっ た。といっても、このことを常に意識していたわけでなく、振り返っ てみると結果的にそうなっていた、という感が大きい。実際、これ までに筆者が開発してきた
- Namazu: 大量の文書を扱う全文検索システム
- Sary: ひとつの巨大な文書を扱う全文検索システム
- Migemo: 日本語をインクリメンタル検索する手法
といった検索システムは、すべて自分が使いたいという動機から生 まれている。本記事では、これらの検索システムを開発する過程で 得られた知見や、活用する上で考えたことなどを整理しながら、検 索技術について考えてみたい。
検索技術いろいろ
ひとくちに検索技術といってもいろいろな種類がある。Googleの ようなウェブの検索や、eコマースサイトでの商品の検索、画像処 理による顔検索といったものまで多種多様である。ここではテキス ト情報の検索に関連する
- 文字列検索
- 情報検索
- 検索インタフェース
の 3つの技術を取り上げ、それぞれについて簡単に紹介しながら、 技術のどういった側面が大切なのか検討してみたい。
文字列検索
ソフトウェアの開発に携わっていると、文字列という言葉に自然と 馴染んでしまうが、実は国語辞典には載っていない専門用語である。 文字列はテキストか文と捉えておけば差し支えなく、文中から特定 の言葉 (キーワード) を探し出す処理を文字列検索と呼ぶ、と考え ればよい。
文字列検索の手法は大きく2つに分類される。ひとつはテキストを 頭から読み進めながら検索する手法、もうひとつは処理を高速化す るために、テキストとは別のインデックス (索引データ) を用いて 検索する手法である。ここでは前者をシーケンシャルな文字列検索 と呼び、後者をインデックス使用の文字列検索と呼ぶことにする。
シーケンシャルな文字列検索
シーケンシャルな文字列検索をもっとも単純に実装すると、テキス トの先頭からはじめて、キーワードとテキストがマッチすれば成功、 見つからなければ 1文字進める、というアルゴリズムになる。この とき、キーワードとテキストが途中までマッチして最終的に一致し なかった場合に注目すると、処理に無駄が生じていることがわかる。
単純な文字列検索
このような無駄を省いて処理を高速化するアルゴリズムとしては Knuth-Morris-Pratt (KMP法) や Boyer-Moore (BM法) が古典的で ある。近年では、Shift-Or アルゴリズムも、プログラムとして実 装した際の処理の効率のよさで知られている*1。
さきほどの例では「検索技巧」の検索は失敗に終わったが、一文字 くらいの違いは許容して検索を行いたい場合もある。このような検 索を曖昧検索と呼ぶ。日常的にコンピュータを使っている場面で曖 昧検索はあまり見かけないが、市販の電子辞書には、うろ覚えの綴 りでも単語が見つかるように曖昧検索に対応しているものが多い。
曖昧検索とは別に、「検索○○論」のように漠然とした指定で検索 したい場合もある。これを可能とするのが正規表現による検索であ る。正規表現の検索に対応したツールは Unix の grep コマンドが 有名である。grep で「検索.*論」で検索すると「検索不要論」に も「検索万能論」にもマッチさせて検索できる。
インデックス使用の文字列検索
インデックス使用の文字列検索でもっとも一般的なのは、書籍の索 引と同様に索引データを作る、転置ファイルという手法である。文 中に現われるそれぞれの単語がどの位置に出現するかの表を作り、 検索に利用する。
このとき、単語の区切りが明白ではない日本語の文の場合は、形態 素解析システムを使って「単語|の|区切り|が|明白」のように分割 したり、2〜3文字づつ (n-gram と呼ばれる) をひとかたまりにし て「単語」「語の」「の区」「区切」「切り」のように分割して索 引を作成する。
形態素解析システムを利用した手法は未知語に弱く、また「モーニ ング娘。」のような言語的によくわからない言葉の解析にも弱いた め、検索に漏れが発生しやすいという欠点を持つ。一方、n-gram の手法は「パン」で検索して「ルパン」が見つかるという欠点があ るが、検索の漏れが発生しにくいという利点は大きい。
筆者が開発を始めて現在はグループで共同開発を行っている Namazu *2 という検索システムでは形態 素解析システムを採用している。そのおかげで、インデックスを小 さく、処理を単純にすることができたが、検索に漏れが生じやすい ことを考えると、正しい選択だったのか疑問が残る。この辺りのト レードオフは検索システムを設計する上で大変難しいところである。
インデックスの形式には他にもさまざまなものがあるが、その中で も Suffix Array はデータ構造が極めて単純で扱いやすいという利 点を持っている。筆者が開発した Sary*3という検索システムは Suffix Array を利用して、巨大なテキストファイルの高速な検索 を実現している。巨大なテキストファイルを扱う場面はさほど多く ないが、論文データベースからの例文の検索や、ゲノムデータベー スを検索する用途などに Sary は応用されている。
インデックスの得失
インデックス使用の文字列検索はシーケンシャルな文字列検索より 高速である反面、インデックスを事前に作成しておく手間がかかる。 対象のテキストが小規模の場合はシーケンシャルな文字列検索で十 分な場合が多いが、規模が大きくなるにつれてインデックスを導入 する必要が生じる。インデックスの導入にあたっては、ディスク消 費量の増加やシステムの複雑化といった導入にともなうコストをふ まえて、速度とのトレードオフを検討しなければならない。
インデックスの必要性はテキストの規模に加えて、どのくらい頻繁 に検索を行うかにもよって変わってくる。月に 1 回しか検索要求 がないような用途であれば検索に数分かかっても不都合はないかも しれないが、毎秒何十件もの検索要求がある用途では、とにかく速 くする必要があるだろう。
一般に、インデックスの更新は時間を要するため、1日1回や1時間に 1回といった間隔で更新されることが多い。この結果、更新間隔の間 に作成された文書が検索にヒットしないという問題が起きる。これ に対する理想的な解決策は、文書が作成・更新されたタイミングで インデックスを更新し、常にインデックスを最新に保つことである。 既に Windows には、格納したファイルから自動的にインデックスを 作成する技術が導入されている。今後はこうした仕組みが OS やミ ドルウェアにさらに広く採り入れられていくと考えられる。
情報検索
文字列検索が字面の検索にとどまっているのに対し、情報検索はテ キストを情報として捉えて、より意味のある検索を行おうという試 みである。
大量の文書から必要な情報を検索する際に、単純な文字列検索では、 キーワードにヒットする文書が多すぎて検索結果が役に立たないと きがある。このような場面で大切なのは、見つかった文書を重要な 順にランキングする技術である。情報検索の分野では古くから、ど のように文書をモデル化し、どのように検索結果をランキングする かについての研究が盛んに行われている。文書のモデル化とは，文 書という具体物を抽象化して、コンピュータが数理的に扱えるよう にする処理のことを指す。
文書をモデル化する手法で最も一般的なのは、文書と質問文をとも に単語の集合からなるベクトルとして捉えて、ベクトル間の類似度 を元に検索を行うベクトル空間モデルである。ベクトル空間モデル では、重要な単語に大きな重みを、瑣末な単語に小さな重みをつけ る計算法がランキングの良し悪しを決める要因となる。広く使われ ている tf idf (term frequency, inverted document frequency) という計算法では、たくさんの文書に含まれる一般的な単語は重要 ではない、少数の文書に含まれる希少な単語は重要である、という 経験的な考え方に基づいて重みの計算を行う。
情報検索の技術には他にも、単語のベクトルの中から同じような概 念を表現する単語を自動的にひとつにまとめて扱い、質問文と文書 の単語が正確に一致しなくても検索を行えるようにした LSI (Latent Semantic Indexing) といった手法や、ニューラルネット ワークを使ったモデル化の手法などもある。しかし、どの手法も基 本的にテキストを統計的に扱うものであり、人間が文章を理解する ようにテキストの意味を解析するシステムには程遠い段階にある。
テキストそのもの以外の情報 (メタデータ) を情報検索に使う手法 も広く利用されている。メタデータの利用はウェブの検索エンジン で古くから行われており、HTML の構造に着目して <title> ... </title> の中に含まれる単語に重みをつけたり、<meta name="description" content="ページの説明文"> の内容を重視し たりといった処理は一般的に行われてきた。しかし、こうした工夫 だけでは検索の質はあまり向上せず、Googleの登場以前は、冒頭 の「情報の氾濫が深刻化して必要な情報を見つけ出せなくなる」と いう状況が長く続いていた。
こうした状況を改善するために、Googleが着目したメタデータは リンクの情報である。ウェブ上のページ間には文字通り蜘蛛の巣 (ウェブ) 状にリンクが張られており、価値のあるページには多く のリンクが張られる傾向がある。Googleの PageRank という手法 は、この性質を活かして、リンクをページの推薦とみなし、多くの サイトからリンクされているページは価値が高い、という考え方に 基づいてページの重要度を計算する。このとき、単にリンクの数だ けではなく、重要なページからのリンクほど価値が高い、という価 値の伝播を含めて重要度の計算を行っている点が PageRank の優れ た点である。
Google はこの PageRank とともに、ページ内でのキーワードの出現 位置といった他の指標を組み合せて検索結果のランキングを行って いる。PageRank がすべてではなく、他のランキングアルゴリズムと の絶妙な「ブレンド」が、Google の優れた検索結果の秘訣である *4。
情報検索の要素技術は、検索の問い合わせに対して結果を返すとい う伝統的な検索システムだけでなく、単語の使われ方から文書の類 似性を調べて類似文書を自動分類する用途や、大量の文書から興味 深い知識を発掘するテキストマイニングの用途などにも応用されて いる。こうした技術を駆使して文書内の知識を活用しようという試 みはナレッジマネジメントと呼ばれ、現在、ビジネス化が急速に進 んでいる分野である。
検索インタフェース
検索の使い勝手を決める重要な要素に、検索インタフェースがある。 どんなに検索が速くて精度がよくても、インタフェースが使いにく ければ台無しになってしまう。ここではアプリケーションの検索機 能とウェブの検索について考えてみたい。
アプリケーションの検索機能
ワープロやブラウザ、メーラなど、大抵のアプリケーションに検索 機能は備わっている。しかし、メニューの「編集→検索」で表示さ れる検索ダイアログはこの10年間、進歩しているように見えない。
伝統的な検索ダイアログ
そもそもこのダイアログは表示するだけで手間がかかって検索の意 欲をそがれるが、なにより呆れるのは、検索結果がこのダイアログ の下敷になって隠れてしまうことだ。一瞬、何も見つからなかった のかと思ってダイアログを閉じると、その下にヒットした言葉が見 つかったりする。
この不便さについて考えていくと、「そもそもユーザは検索などあ まりしないのだから検索ダイアログなど使いにくくてよい」という ドグマに思い当たる。使われない機能なら手を抜いたっていい、と いう考え方だ。しかし、実態は「検索ダイアログが使いにくいから ユーザは検索をしないだけだ」の方が近いのではないだろうか。
Unix で広く使われている Emacs というエディタは複雑怪奇な操作 体系を持つ、決して素直には使いやすいと言えない代物だが、検索 機能は優れている。ミニバッファと呼ばれる画面の最下部の領域を 使って検索したい言葉を入力するため、ダイアログに邪魔されるこ となく検索を行うことができる。さらに優れている点は、キーボー ドを1 文字打つたびに検索が進行することだ。
インクリメンタル検索
この例では sch と最初の 3文字を打つだけで scheme という言葉の 検索に成功している。このような検索はインクリメンタル検索と呼 ばれ、古くから存在している。マッキントッシュのユーザインタ フェースの産みの親の一人とされるジェフ・ラスキン氏は、インク リメンタル検索を重視し、インクリメンタル検索専用のキーを備え たワープロ専用機の設計を行っている。氏によれば、インクリメン タル検索は検索がすばやく行えるだけでなく 1打鍵ごとにユーザに フィードバックが返るという点においても優れているとのことだ。
筆者が開発した Migemo *5という ソフトは、このインクリメンタル検索を日本語でも行えるようにし たものである。日本語特有のかな漢字変換のステップを省略し、ロー マ字のまま日本語をインクリメンタル検索できる。下の例では kik と最初の3 文字を打つだけで「奇怪」という言葉の検索に成功して いる。
日本語のインクリメンタル検索
検索ダイアログを表示しないことも、インクリメンタル検索にして も、ちょっとした工夫にすぎないが、このことはずいぶん長い間な いがしろにされてきた。しかし、ここにきて、検索不遇の時代にも 変化が訪れ、検索機能は「編集→検索」という不当な扱いから抜け 出し、表舞台に姿を現し始めている。その端的な例は、Mac OS X のメーラに見て取れる。Mac OS X のメーラでは、検索用のフォー ムを常に見えるところに表示し、インクリメンタル検索にも対応す るというインタフェースを採用している。
Mac OS X のメーラの検索機能
これまでのメーラは、検索機能が奥に隠れていたため、検索はあま り利用されてこなかった。その結果、検索の代わりに、件名や差出 人順でソートして目的のメールを目視で探す、といったことがごく 日常的に行われてきた。検索機能が表に出るだけで、こうした迂遠 な操作を行う必要がなくなり、目的のメールを本来的な方法ですば やく見つけ出すことができる。
検索ダイアログの欠点を最後にもう一点挙げると、いちいちクリッ クしないと次の位置を見ることができないという問題がある。ぱっ と一目見るだけでまとまった情報を識別できるという人間の特性が まったく活かされない。この点も、近年では改善が見られるように なり、Googleツールバー *6 は、指定した言葉をブラウザ内でハイライト表示する機能を持って いる。このような工夫もテキストビューアなどで古くから行われて いたが、不思議と広く日の目を見ることはなかった。ハイライトに よって検索結果の表示に一覧性がもたらされ、検索の有用性が大幅 に向上する。
Googleツールバーのハイライト機能
ウェブの検索
Googleはランキング技術だけでなく、検索結果の表示手法も優れ た検索エンジンである。Googleの検索結果では、検索に指定され たキーワードがサイト内でどのように使われているかをサイトの要 約として表示している。このような表示手法は KWIC (KeyWord In Context) と呼ばれ古くから存在していたが、処理のコストが大き いため、Google以前の検索エンジンではあまり利用されてこなかっ た。ページの冒頭部分を要約として表示する手法と比べて KWIC 式 の表示は有益な情報を多く含んでいる。
Googleの検索結果
検索エンジンを利用していると、検索結果の最初の数件だけでなく、 もっと多くの検索結果を効率的に閲覧したいという場合もある。 「日経バイトのサイト」を検索するときは検索結果の最初の 1件だ けで十分かもしれないが、「日経バイトの評判」を調べるときは大 量の検索結果を閲覧したい。このような用途で効率的に検索を行う ためにリストブラウザ *7というソフトが 考案されている。
リストブラウザ
ウェブの検索は成熟した感もある分野だが、インタフェースという 観点からは、依然としてフォームにキーワードを入力して送信する とサーバから結果が返ってくるだけ、という状況が続いている。今 後は、インクリメンタル検索をはじめとする対話的な手法の導入に よって、操作感や視覚的な面での使いやすさが改善されることが望 まれる。
情報管理の顛末
冒頭で自分の興味の中心は「自分の情報を組織化し、自分がその情 報を利用できるようにすること」と述べた。ここではその結果どう なったのか顛末を振り返ってみたい。
Namazu を使わなくなった理由
Namazu の開発を始めたのは今から 6年前の 1997年のことである。 当時はインターネットに熱中して、ロック関連の情報をあさってお り、手元に集めてきた情報だけでもかなりの量になっていた。これ を効果的に検索しようと思って開発を始めたのが Namazu である。
Namazu を公開すると、興味を持ってくれる人が予想以上に集まり、 中小規模のサイトの検索システムとして徐々に使われるようになり はじめた。その一方で、溜まっているメールの検索といった個人用 途の検索システムとして使いたいという人も現われるようになった。 当時、多くの技術系のメーリングリストに参加して情報収集と情報 交換を行っていた筆者は、メーリングリストのアーカイブを快適に 検索できたら便利だと思い、さっそく導入して手元で使い始めた。
しかし、時間が経つにつれてわかってきたのは、メーリングリスト の情報源としての価値が急激に低下し始めたことだ。ウェブを検索 すれば多くの情報が得られるようになったため、わざわざメーリン グリストのアーカイブを検索することは稀になった。検索が稀であ れば、1 回の検索に数十秒かかってもそうは気にならない。こうし て結局、手元のメールの検索に Namazu を使うのはやめてしまった。
一方、数年前までは、個人的なメモをトピックごとにファイルを分 けて、検索に Namazu を利用するという情報管理を行っていた。し かし、トピックの分類に頭を悩ませるようになって、あまりいい方 法ではないと気づき、これもやめてしまった。
このような経緯を経て、開発を始めた当人でありながら、自分で Namazu を利用することはほとんどなくなってしまった。これは別 に Namazu が無用ということを意味するのではなく、筆者の個人的 な用途にはインデックスは不要だった、ということだ。
ChangeLogメモ
トピックごとにファイルを分けるメモの管理をやめてからは、 ChangeLog と呼ばれる形式で 1つのテキストファイルにメモを取る 「ChangeLogメモ」*8 を始めた。エディタのショー トカットキーひとつで手軽にメモを取れるため、4 年間、順調に続 いている。
このメモは、 4年間で 5万行、1.7MB 程度の大きさになった。この くらいであれば、エディタの検索機能でも十分な速度で検索できる。 Emacs なら M-x occur という機能を使って検索結果を一覧表示し て目的の位置へ移動することが容易にできる。以下は「Ruby:」と いうキーワードで検索した結果の一部である。
122: * Ruby: Enumerable#inject の使い方 126: * Ruby: 配列をシャッフルする方法 132: * Ruby: shift は O(n) 514: * Ruby: mathn を require すると、数値演算の挙動が変わる 830: * Ruby: ruby -I /somewhere を Rubyスクリプト内で行う方法 2465: * Ruby: Object#send を覚える。これは便利 4616: * Ruby: IO#sync = true でバッファリングを抑制できる 4654: * Ruby: 日本語の tr には require 'jcode' が必要
ChangeLog メモは単なるテキストファイルであるため、図や写真を 張り付けられないという大きな欠点があるが、エディタからすばや くメモを取れるという点と、ファイル形式の互換性を心配する必要 がないという利点は大きい。
まとめ
自分の情報管理を振り返ってわかったことは、ハイテクからローテ クへと後退している、ということだ。インデックスを使用する方が 技術的に高度であり、インデックスを使わなくなったことは、ロー テクへの後退といえる。しかし、こうしてシンプルな情報管理の方 法へ移行したことによって、実質的な利便性は高まっている。検索 技術は適材適所が肝要であり、シンプルな手法で済むところに大掛 かりな手法を持ち込む必要はない、というのが教訓である。
かといって、現状に不満がないわけではない。ChangeLogメモは、 単に時系列にメモが並んでいるだけであり、情報を組織化するとい う点では、まったくものたりない。Googleがウェブの検索にもた らしたのと同様の革新を個人の情報管理に起こせないか、今後も検 索システムの開発に取り組みながら、考えていきたい。
コラム: 2つの法則
本記事を書くにあたって、検索とは何かについて改めて考えてみよ うと試みた。最初にしたことは、平凡に辞書で「検索」を引くこと、 次はGoogleで「検索」を検索することだった。考えてみようと思っ て最初にしたことが 2つとも検索だったことから、ひとつの仮説が 浮かんだ。もしかしたら「考える」という行為を「検索」で代用し ようとしているのではないか。
調べて考えることは大切と言われる。現在はGoogleや電子辞書の おかげで、調べることはずいぶん簡単になった。しかし、その分、 考えることに時間を費やすようになったかというと、そうでもない ようだ。レポートを書く代わりに、似たようなレポートをウェブで 検索して少々修正を加えて提出する、という行動は端的な例かもし れない。このことから、
「調べることは簡単になっても、考えることは簡単にはならない」
という法則を思いついた。これはなかなかよくできた法則だと思っ て喜んでいたところ、ちょうど知人から一通のメールが届いた。あ きれるような質問だった。調べればすぐわかることをわざわざ訊く な、と腹が立った。そして、このことから、
「調べることは簡単になっても、調べるとは限らない」
という第二の法則の発見に至った。自分だって人のことは言えない。 我ながら耳が痛い法則である。
コラム: 検索と記録社会
検索はメールに続いて第2位のオンライン活動であるという調査報 告 *9 がある。調査の信憑性はよくわからないが、検索が頻繁に行われて いるということには実感がある。試しにGoogleで「検索」「メー ル」「インターネット」を検索してみると、
インターネット: 約94,200,000件 検索: 約94,100,000件 メール: 約85,000,000件
という順にヒット件数が並ぶことがわかった。「検索」が「メール」 より上なのはやや意外だったが、考えてみると、このコラムを書く ためにも最低でも 3回は検索をしており、検索がメールより上位に 来るのも実感としてうなずける。もはやネットの検索なしの生活は 考えられなくなった。
このように検索が日常生活に定着するにつれて、ネットにおけるプ ライバシの考え方が変わってきている。筆者の友人は就職の面接の 際に、面接官が自分のことを知りすぎているのでいぶかっていたと ころ、「あなたのページを検索して読ませていただいたんだけど」 と言われてはじめて納得したそうだ。この友人の場合はまっとうな 内容のページを作っていたため就職にプラスに働いたようだが、趣 味的な内容の場合はマイナスとなる恐れもある。実名を出す以上は 就職の面接官に読まれることも意識してページを作らないといけな いようだ。
一方、自治体や企業のウェブサイトでは、担当者のミスで個人情報 を含んだ名簿をうっかり載せてしまうという事故が絶えない。「削 除したのでご安心ください」と発表した途端にGoogleにキャッシュ が残っていることが判明して余計に被害が広まってしまったという 事件もあった。Googleのキャッシュは元のサイトが消えてしばら くすれば見えなくなるが、archive.org のアーカイブは元のサイト が消滅してもページ内容を保存し続けるため、さらに厄介である。 知人は、うっかりウェブに載せてしまったサークルの名簿を削除し てもらうよう archive.org に依頼したが、1か月たっても反応がな いそうだ。
ネットに一度載せてしまった情報は、すぐに記録され、簡単に検索 でき、消すことは困難、という性質を持っている。ネット上に何か を載せるときはこのことをよく考えておく必要がある。記録と検索 の技術は今後ますます発展して社会に浸透していくと思われる。筆 者は、このような社会を勝手に「記録社会」と呼んでいる。利便性 の代償として支払っているものは意外と大きいのかもしれない。
参考文献
- Ricardo Baeza-Yates and Berthier Rieiro-Neto, Modern Information Retrieval, Addison Wesley, 1999.
- 馬場肇, Google の秘密 - PageRank 徹底解説, 2001, http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html
- 高林 哲, 横着プログラミング(1) Unixのメモ技術, UNIX MAGAZINE, Vol. 17, No. 1, pp. 117-125, 2002, http://0xcc.net/unimag/1/