研究 → [ 概略 | 論文・発表 | 補助金 | プログラム・デモ | 専門書(洋) | 専門書(和) | リンク ]



高校生向き 研究解説

ウェブの検索とアルゴリズム

はじめに

いまこの文章を読もうとしているみなさんは,自宅や学校で,コンピュータを インターネットに接続して,このページを読み始めたことと思います. それではみなさんは,どのようにしてこのページを見つけましたか? 多くの人は,大阪府立大学のホームページ から,何度か「リンク」をクリックして このページにたどり着いたのではないでしょうか. あるいは,「検索サイト」で何らかのキーワードを入力して得られた検索結果の 中にたまたまこのページがあり,直接見つけたかも知れません.

ウェブを便利な道具として利用することは,もはや日常の一部として当たり前の ことになっています. しかしながら,その誕生(*1)からはまだ15年しか経過しておらず, このわずかの間に,ウェブの誕生当初には想像もできなかったような 機能を次々と実現し,巨大なビジネスを生むまでに成長しました. このような発展は,決して一朝一夕に遂げられたものではなく, そこには情報科学分野の地道な,そしてときには画期的な研究の積み重ねがあり, それらの研究成果が実を結んだものに他ならないのです.

そこで以下では,ウェブに関連してどのようなトピックが大学や民間の研究機関で 研究対象となってきたのかを,ウェブをわれわれユーザにとって 有用な道具にする上で重要な役割りを果たしている検索エンジンを例として とりあげ,その一端を説明します.

(*1) 1990年頃に,Tim Berners-Lee が発明した. 彼は現在,W3C (World Wide Web Consortium)の Director.

ウェブとは

ある対象物どうしが何かで結ばれてできる構造を,ネットワーク(網)といいます. たとえば,都市どうしが道路で結ばれてできるのが道路交通網です. いま,世界中の多くコンピュータどうしは,プロバイダなどを経由して 光ケーブルや電話回線などで結ばれています. このように,コンピュータどうしの物理的な接続によってできる ネットワークをインターネット(the Internet)といいます.

インターネット上のコンピュータでは, 文書をはじめとする数えきれないほどの情報が, ホームページなどで世界に向けて公開されており, これらは他のホームページなどを参照することによって,互いに結ばれています. このようにしてできるネットワークを, ウェブ(the World Wide Web; WWW)といいます. われわれは通常,ウェブ上で公開される情報を閲覧ソフト(ブラウザ)を用いて 見ていますが,そのときブラウザに一度に表示される情報の単位を (ウェブ)ページと呼び,ページからページへとクリックで移動して 参照できる仕組みを(ハイパー)リンクと呼んでいます. すなわちウェブとは,ウェブページどうしがリンクで結ばれた,インターネット上の 仮想的なネットワークという訳です.

たとえば,いま表示されているこのページは, このリンクによって私のホームページの表紙を参照し 結びつけられています. このようにウェブページは,普通の書物の1ページとは異なり, リンクという他のウェブページを指し示す目印(アンカー)を含んでいることが 最大の特徴です.

ウェブにまつわる素朴な疑問

ウェブがどのようなものであるかを簡単に説明したところで, ここではウェブに関して誰もが抱きそうな素朴な疑問を いくつか取り上げてみます.

ウェブの規模

ウェブ上には数えきれないほどの情報があると書きましたが, ウェブページという単位で数えると,いったい全部で何ページくらいあるでしょうか.

実は,世界中で少なくとも約80億ページがあるとされています. この数値は,世界の人口規模(推定64億人)と大きくはかけ離れてはいません. しかしながら,ウェブの誕生と人類誕生からの歴史の長さを比べると, ページ数の増加率は人口増加の比ではありません. ちなみに,ここ数年のウェブページの総数の下限の推移を見ると, 2000年には約20億であったものが,
    2003年:約33億,
    2004年:約42億,
    2005年:約80億
と,その増加の勢いは爆発的であることが分かります. それでは,いったいどのようにしてウェブ上に存在するすべてのウェブページの 総数を求めることができるのでしょうか.

リンクの構造

もしみなさんが, 大阪府立大学のホームページ からこのページまでリンクをたどって 到達したのであれば,いったい何回リンクをクリックして訪問したでしょうか. 10回ですか,あるいは 5回でしょうか.最短では何回で到達できると思いますか? ちなみに,正解は7回です(*2). この7回という回数は,意外に多いと感じるかも知れません.

ところが,これとは逆の事実も観察されています. たとえば,あなただけが知っているようなお気に入りのウェブページを 1つ思い出してください.いま,現在見ているこのページ (S) から, あなたが思いついたページ (T) まで,各ページ内にあるリンクだけをたどって (最短の行き方で)たどり着こうとするとき, いったい何回のクリックが必要だと思いますか? これについては,一般にどのページからどのページへでも, 最悪でも16回〜20回のクリックでたどれることが知られています (*3) [KS01].

また, 私のホームページ 自身も,ウェブ上で確認されているという少なくとも 80億はあるウェブページの 1つですが,世の中にはリンクをたどっているだけでは どうしても到達できないページも存在し,その数は全ウェブページの10% 程度は あるということも知られています [BKMRRSTW00]. ウェブのこのような性質は,どのようにして調べるのでしょうか.

検索

みなさんは,ウェブで調べものをしたり,分からないことを解決しようと思ったときに どうしますか? そのようなときには,むやみにリンクをたどって答えを探すのではなく, きっと Yahoo!Google など, 検索インターフェースを備えるページをもつ サイト(検索サイト)を 利用して探すのではないでしょうか. あっという間に検索結果が得られて,調べたかったことが分かったり, あるいは思いがけない情報を知ることができたりして, 結果に満足できることが多いかと思います. では, Yahoo!Google は, あなたの問合せに対する答えを,いったいどのようにして見つけて いるのでしょうか.


以上,ウェブに関して思いつく素朴な疑問を,例として3つ取り上げましたが, これらはすべて学問として研究の対象となり得るものであり, 実際にその多くが情報数理科学の分野の基礎技術を用いて解決されているのです. これ以降の節では,ウェブにおける検索,とりわけ検索エンジンについて 少し詳しく見ていきます. なぜならば,検索エンジンこそがこれらの疑問に答えるために, 重要な役割りを果たしているからです.

(*2) ウェブ上のリンクは絶えず生成死滅し,日々変化しています. もしこれより少ないクリック数で到達できた人があれば,ぜひご一報ください. またこれとは逆に,このページから大阪府立大学のホームページへは, 1回で到達することができます.
(*3) ただし,S から T までたどる行き方が存在することは仮定する.

検索エンジンと Google

検索インターフェースをもつウェブページを提供するのが 検索サイトであるのに対して, ユーザが調べたいと思って入力したキーワードに対して, それに合致するページを実際に探し出してくるメカニズムを 検索エンジンと呼びます.いわば,縁の下の力もちです. たとえば Google は, 検索サイトの名前であるのと同時に, 同社が設計・開発する検索エンジンの名前でもあります. その一方で, Yahoo! というポータルサイトは 検索サイトではありますが, 2000年から2004年までは,自身では検索エンジンを持っておらず, Google のものを利用していました.

このような検索エンジンの使命の一つは, ユーザが調べたいと思って入力したキーワードに対して,
    1. 的確な結果を,
    2. 高速に
検索して提示してくれることにあります. これらの2つの項目がともに大切であることはもちろんですが, ここでは(1)の的確な結果を検索する能力に注目してみます. 的確さを実現するためには,より詳細に分析すると,少なくとも次の2つの能力が 必要となります.

検索エンジンの歴史の中で,この目的が達成できないものは次々と厳しく 淘汰されてきました(*6). そんな中で,1998年に設立され 2000年に世界一になった(*7) Google は, それ以降2005年現在までの 5年間という長きにわたり, 不動のチャンピオンの座と名声を獲得していますが, それは,上記の要求を常に高いレベルで満たす機能を 実現し続けているからに他なりません.

(*4) ちなみに,Google で 「大阪府立大学」をキーワードとして検索すると, 0.21秒で検索が終了し,その検索結果は 119,000件ありました. 他の検索エンジンでは,例えば Yahoo! では 69,165件,MSNサーチ では 27,512件でした.
(*5) 同様に,Google で「大阪府立大学」をキーワードとして検索すると, 大阪府立大学の公式ホームページが 119,000件中 1番目に表示されました.
(*6) たとえば,infoseek や AltaVista など.
(*7) これは,後で述べるインデックス化されたページ数の意味で.

検索を支える基礎技術

ウェブページの収集

現在その存在が確認されているウェブページの総数が約80億であることは 先に書きましたが,これはどのようにすれば数えらるのでしょうか. すぐに思いつく方法としては,例えば 大阪府立大学のホームページから 始めて, そのページにあるすべてのリンクをたどって新しいページを発見し収集する ということを延々と繰り返せば, やがては新しいページが見つからなくなって,すべてが数えられると思うかも 知れません. これはまさにそのとおりであり, 検索エンジンが実際に行なっているのも,この地道な作業に他なりません. このように,実際にウェブ上に存在するページを1つ1つ収集して番号を付け, 収集したデータを組織的に格納・保存することを, ウェブページのインデックス化といいます. 検索エンジンは,ウェブ上のページを収集し,手元に持つことによって, さまざまな検索に対して即座に答えられる仕組みを実現しているのです.

何だ簡単なことではないか,と思った人も多いかも知れません. しかしながらこれは,言うは易く行なうのは極めて困難な作業なのです. 例えば,1秒につき1ページの割合いで新しいページを発見して,それを インデックス化できるとしても,80億ページをインデックス化するには, 単純計算で250年以上かかります. このような作業は人間が行なうのは到底不可能です. そこで,ウェブ上のリンクを昼夜を問わずたどって動き回る, 自動化されたプログラムが必要となります. このようなプログラムは,クローラ(crawler)あるいはウェブ巡回ロボットなどと 呼ばれます. 確かに,ただリンクを次々とたどるプログラムを設計するだけなら,ある程度の プログラミングの知識があれば可能のように思えます. しかし,下手なプログラムだと, 同じページばかり繰り返し訪れて,なかなか収集ページ数が増えないかも 知れませんし,動作も非常に遅いかも知れません. ウェブ上のページを効率的に収集するためには,極めて高性能なクローラが 不可欠となります. したがって,その設計には,プログラミング以外にもさまざまな情報科学の 知識が必要となり,各検索エンジンがしのぎを削る舞台であり,設計者の腕の 見せ所なのです.

このため,検索エンジンがインデックス化に成功しているページ数は, そのまま検索エンジンの性能を表す一つの重要な指標になります. 検索エンジンには,自身がインデックス化したページ数を公表するものが 多いのですが(*8), その中で Google は約 80億ページを手に入れ, Yahoo! を始めとする他の追随を許さない状況が続いています. ちなみに,Google の検索エンジンでさえ到底すべてのページを 網羅しているとは言えず,最新の研究では, 2005年 1月末現在のインデックス化可能な ウェブページの総数を 115億以上であると見積もっています [GS05].

ウェブページのインデックス化にあたっては,他にもさまざまな技術が 必要となります. たとえば,クローラが収集した 80億ものウェブページに書かれた情報を, (検索可能な状態で)格納・保存しておくことを考えてみましょう. そのデータの量は,いったいどの程度の大きさでしょうか.

朝日新聞 2005年5月1日付けの記事 [A05] によると, 2004年2月現在,日本のページ(URLの末尾が○○.jp であるページ)だけで, 約 8500万ページ,13テラバイト(TB)のデータの大きさがあるそうです. 計算の簡単のため,仮に現在の世界中のウェブページの総数が85億ページで, それらが日本(.jp)のページと同程度の大きさを持つとすると, 単純計算で1300テラバイト= 1.3ペタバイト(PB)の大きさがあることになります. これは,1台100ギガバイト(GB)のハードディスクを備える 市販の標準的な PC (コンピュータ) にすべての情報を 格納すると仮定すると,約 13000台の PC が必要となります. 実際 Googleでは,これらのデータを格納するために,数万台もの PC があると 言われています.

「大阪府立大学」をキーワードとする検索に対して,わずか 0.21秒で 119,000件 もの検索結果を返してくれるには,80億ページ分もの情報を,何万台もの PC に どのように格納すればよいのでしょうか. 何万台もの PC は,どのように接続すればよいのでしょうか. いくつかの PC が突然故障してしまったときのバックアップは, どういう仕組みで実現しているのでしょうか. 謎や疑問は尽きませんが,これらを実現する技術も, 多くは情報科学分野の研究成果なのです.

検索結果の提示

大阪府立大学に関する情報が知りたくて,それをキーワードとして検索した 結果が多数あるとき, 公式ホームページ のような本当に知りたい情報は, 検索結果表示画面の 1ページ目に出てきてほしいものです. もし欲しい情報が検索結果の先頭の方にないとすれば, せっかく結果は出ていても, その中から探し出すだけで多大な労力が必要となるでしょう.

われわれがよく利用する検索エンジンは,通常このことを考慮して 検索結果を表示しているので, みなさんはあまり不自由を感じたことはないかも知れませんが(*9), 実はひと昔前の検索エンジンは,必ずしもそうではありませんでした. たとえば,1990年代後半に一世を風靡した AltaVista という検索エンジンは, 与えた検索キーワードに対して,確かに多くの結果を提示してくれて, 当時としては画期的なものでした. しかし,それらの検索結果を取捨選択し,自分が欲しい情報を得るためには, 手作業に頼る必要がありました. ただ,多くの人は検索結果の多さに満足するあまり, その欠点には不満を感じていなかったように思われます.

このように,提示順序に大きな工夫を施さない検索結果だけを提示していた 検索エンジンでしたが,ここに画期的なアイデアを導入したのが, Google の生みの親であり,当時スタンフォード大学(アメリカ)の 大学院学生であった Sergey Brin と Lawrence Page でした. 彼らの考え方は次のようなものでした: 各ウェブページには,そのページ自身が持っている固有の価値や重要性があり, 検索結果は,キーワードに合致するページを重要度の高いものから順に 提示するべきである. 彼らは,この重要度をランク(rank)と呼び,各ページにランクを与える方法として, PageRank(*10) と呼ばれるアルゴリズム(*11)を 考案したのです [BP98, PBMW99].

実は,ひと昔前の検索エンジンも,提示順序にはある程度の工夫がない訳では ありませんでした. ただその工夫とは,重要度の高さを「検索に用いられたキーワードを 多く含むページとする」という程度の,素朴なものでした. しかしながら,このような単純な尺度だと,必ずしもうまくは働きませんでした. たとえば,重要そうなキーワードを目に見えない形で数多くページに 埋め込むことによって, 重要度を人為的に高くして,検索結果表示ページの先頭の方に表示させることが できたりしたのです.

それでは,Brin と Page が考案した PageRank アルゴリズムは, どのようなアイデアで何が素晴らしかったのでしょうか. それは,ランク(重要度)の高いページを次のように定めたことにあります:
    「より多くのしかも良質な(高いランクの)ページからの 厳選されたリンクを受けているページである」
この定義から分かるように,各ページのランクは,入力されるキーワードや キーワードの頻度とは無関係に,リンクの構造だけに依存して 事前に計算することができます.そして検索時には,キーワードを含む ページの中から,原則としてランクの高いものから順に表示します. したがって,キーワードの埋め込みによって,人為的にランクをあげることは できなくなり,より客観的な基準を与えることに成功したのです. 一見単純と思えるランクの定義ですが,これが驚くほど上手く働き, 検索結果を非常に的確な順序で提示することができるようになりました. Google は,このアイデア一つで他の検索エンジンとの競争に勝利し, 大成功を収めたのです.

では,実際に PageRank アルゴリズムが,各ページのランクを計算するには どのようにするかというと,それは, 行列の固有値を計算することで求められることが知られています [B03]. ここでは,アイデアを実現する手段として,数学の知識が必要となります. ちなみに, Google は,インデックス化したすべてのページに 0から 10の 11種類のランク (10が高く,0が低い)を与えるのですが, ランクが 10のページはめったにありません(*12)

(*8) Google のトップページの構成は 非常にシンプルなものですが,そのページには 「8,058,044,651ウェブページから検索」 という表示があります(数字は随時更新される). これは,Google が最も優秀な検索エンジンであることを誇示するメッセージです.
(*9) 「大阪府立大学」をキーワードとして検索すると, GoogleYahoo!MSNサーチのいずれでも, 大阪府立大学の公式ホームページが,検索結果の 1番目に表示されました.
(*10) PageRank アルゴリズムは,たしかに(ウェブ)ページのランク(重要度)を 計算するアルゴリズムですが,その名前は, ウェブページの"ページ"ではなく,考案者の一人である L. Page から とられたものです ( http://www.google.co.jp/intl/ja/press/funfacts.html ).
(*11) アルゴリズムとは,ある目的を達成するためにコンピュータが実行する 機械的なステップが正しく動作するための原理.
(*12) 実は,いま読んでいるこのページからリンクがあるウェブページの中に, ランクが 10のページが1つだけあります.

おわりに

本文中にも書いてきたように, いま検索エンジンの世界では,そのクローラの情報収集能力と PageRank アルゴリズムの優秀さで,Google がチャンピオンとして君臨しています. 確かに,Google の技術は現時点で完成されたものと思えますが, その検索結果には欠点も指摘されています. 検索だけでも巨大な市場を形成している現在, 他の検索エンジンも,Google の一人勝ち状態に決して手をこまねいている訳では ありません.

たとえば,上位をうかがう新興勢力として Teoma という検索エンジンを持つ Ask.jp という検索サイトがあります. Teoma は,ページの重要度に新しいアイデアを持ち込んだり, サイトにいろいろな新機能を導入するなどの 工夫をしています(*13). 個人的な感想としては,検索結果はまだ先行勢力には及ばないというのが 正直なところです. しかしながら何よりも新鮮で驚いたのは, 最近 Ask.jp が, 検索サイトとして TVコマーシャルを流していたことでした. このこと自身が,ウェブの検索が巨大な市場であり, まだまだ新しい研究成果が期待できる分野であることを物語っていると思います.

この解説では,情報数理科学の分野ではどのようなことが研究のトピックとなるか, また,それらが情報数理科学のどのような基礎技術で解決されているのかを, ウェブや検索エンジンの世界を例として取り上げて見てきました. その一端でも分かってもらえたでしょうか. 学問として非常に若く,技術も日進月歩である情報科学の分野は, アイデア一つで大きな貢献ができる研究分野です. その一方で,思いついたアイデアを実現するためには, 高校で学ぶ数学,大学で初めて学ぶ情報科学やそれに必要な 新しい数学,アルゴリズムの設計技法やプログラング,コンピュータの仕組みなどの 知識が複合的に必要となることも分かったかと思います. この文書を読んで興味を持ち,大学でこのような分野を勉強しようと思って 入学してくれる人が一人でも増えれば幸いです.

(*13) 工夫の詳細は, ここ

参考文献

[A05]
朝日新聞ウェブ記事, 国会図書館,ネット情報収集へ 保存して一般公開. http://www.asahi.com/digital/internet/TKY200504300227.html,2005.
[B03]
馬場 肇, Googleの秘密 ― PageRank徹底解説, http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html,2003.
[BKMRRSTW00]
A. Broder, R. Kumar, F. Maghouul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins and J. Wiener, Graph structure in the Web. Computer Networks, 33: 309-320, 2000.
[BP98]
S. Brin and L. Page, The anatomy of a large-scale hypertextual Web search engine. http://dbpubs.stanford.edu:8090/pub/1998-8, Computer Networks 30: 107-117, 1998.
[GS05]
A. Glli and A. Signorini, The indexable Web is more than 11.5 billion pages, Proceedings of the 14th International WWW Conference, 2005.
[KL01]
J. Kleinberg and S. Lawrence, The structure of the Web. Science, 294: 1849-1850, 2001.
[PBMW99]
L. Page, S. Brin, R. Motwani and T. Winograd, The PageRank citation ranking: bringing order to the Web, http://dbpubs.stanford.edu:8090/pub/1999-66, 1999.



[ホーム] [プロフィール] [研究] [教育] [コンピュータ] [その他] [リンク] [更新情報] [サイトマップ]
[大阪府立大学] [理学系研究科] [情報数理科学専攻]