最近はいよいよ自分の就職活動が本格化してきて、かなりナーバスな今日この頃です。そんなわけで、Blogのエントリーでも書いて気分転換をしようということで、今回は探索アルゴリズムの基礎についてごく簡単にではありますが、まとめてみようと思います。

探索アルゴリズムとは

探索アルゴリズムというのは、いわゆるクローラーがWebを巡回する際に用いるテクニックみたいなものです。クローラーというのはリンクを元にWebページを巡回取得していくようなプログラムのことです。検索エンジンの裏側でもクローラーが動いていて、ページを検索エンジンに登録していたりします。なぜここで探索アルゴリズム？と思われるかもしれませんが、2ヶ月ぐらい前から簡易なクローラーをPerlで書いていて、その中で探索アルゴリズムの存在を知ったので、自分にとって確認の意味も含めて今回まとめてみようと思ったわけです。

深さ優先探索と幅優先探索

探索アルゴリズムには、一般的に「深さ優先探索」と「幅優先探索」の2種類があります。名前の通り、前者は深いほうを優先的に読みにいく方式で、後者は優先的に広く読みにいく方式です。

上の図が２つのアルゴリズムを用いて探索していく順番を示したものです。円で示したものがいわゆるノードで、1つ1つがWebページだと考えてください。また、ノードをつなぐ線がリンクだと考えてください。円の中に書かれた番号が、探索する順番を示しています。「深さ優先探索」ではリンクをたどって深い方を優先的に読みにいき、「幅優先探索」では一番上位のノードからより浅い方を先に読んでいることが分かると思います。

一般的に「深さ優先探索」では、リンクをたどって見つけたノードをスタックに入れて管理します。LIFOの仕組みが探索に向いているというわけです。逆に「幅優先探索」では、見つけたノードをキューに入れて管理します。この場合はFIFOの仕組みが探索にマッチするわけです。

では、2つの探索アルゴリズムを使い分ける必要はあるんでしょうか。もちろんあります。何か特定のWebページを探したい場合に、深さを優先するか、幅を優先するかで、メモリーの使用率が変わってきたりします。この辺は少し難しいところで、自分自身も少し曖昧な所があるので今回はこのぐらいにしておきます。

検索エンジンのクローラー

2つの探索アルゴリズムについて説明しましたが、これらのアルゴリズムを検索エンジンのクローラーにそのまま使えるかというと、実はそうはいかなかったりします。なぜなら、インターネットのような巨大なリンク構造をクロールした場合、リンクがつながっている限り、いつまでたってもクロールが終わらないという問題が起きてしまうためです。このへんの仕組みが、検索エンジンを作る上でも難しい部分のようです。

各検索エンジンの仕組みがどうなっているのか分かりませんが、今回は参考のために、オープンソースの全文検索エンジンであるHyper Estraierのクローラーがどうなっているのかを確認してみました。クローラガイドを読んでみると、Webサイトの類似度をベースにした探索方法を用いていることが分かります。つまり、言語処理とクロール機能を組み合わせて探索を行うというわけですね。

まとめ

最後に簡単にまとめを。Webをクロールするには、探索アルゴリズムを用います。探索アルゴリズムは一般的に「深さ優先探索」と「幅優先探索」の2つが存在します。検索エンジンのクローラーは単純なこれらのアルゴリズムではなく、言語処理機能などを組み合わせたアルゴリズムを使います。

こんな感じに探索アルゴリズムの基礎っぽいことをまとめてみました。空間計算量とかを語れるともうちょっと詳しい事が書けるのですが、自分の中でもいまいちな状況なので、もっと勉強が必要ですね。