質問: 「Webの巡回ソフトを設計する場合、無限ループを回避するにはどのようにすれば良いですか?」 解法 まず、最初に考えるべきことはどのようにして無限ループが起こるのかということです。もっともシンプルに考えれば、ウェブをリンクのグラフと考えた時に、グラフに循環する部分があれば、そこで無限ループが起こると判断できます。 無限ループにならないようにするにはグラフの循環を検出する必要があります。解決策の一つはハッシュテーブルを用い、vというページにアクセスしたらhash[v]をtrueにしながら進めていく方法です。 これを用いて、ウェブページを幅優先探索により巡回しましょう。ウェブページを訪れる鉢に、そこからのリンクをキューに追加します。もしアクセスずみのページがあれば、無視します。 これは良い方法ですが、ウェブページvにアクセスするというのはどういうことでしょうか?ウェブページvはそのコンテンツで定義されるのか、URLで定義されるのか、どちらでしょうか? URLで定義されるとすれば、URLのパラメータが完全に別のウェブページを示していることを確認しなければなりません。また、パラメータはそのウェブアプリケーションが認識できない、あるいは取り扱うことのできないものでも、ウェブページの内容を全く変えることなく、好き勝手に付け加えることができます。 コンテンツで定義するとすれば、あるホームページでコンテンツがランダムに生成されていると考えてください。そこは、訪れるたびに異なるページと言えるのでしょうか。そうではありませんね? 現実的には「異なる」ページを定義できそうにありません。そしてこの部分がこの問題を扱いにくくしている点です。 この問題に取り組む一つの方法としては、ページの類似性についてある程度の推定を行うことです。コンテンツとURLの両方をベースとして、あるページが他のページと十分にていると思われれば、そのページの子ページは巡回の優先度を下げるようおにします。各ページにコンテンツとURLに基づいたある種のシグネチャを取り入れます。 例えば、どのようにすればいいかを見てみましょう。 巡回する項目のリストがデータベースに保持されています。その中でもっとも優先度の高いページを選んで巡回していきます。この時、次のようにします。 1. ページを開き、内容の一部とURLをもとにシグネチャを作る。 2. 最近このシグネチャによるアクセスがあったかどうかを調べるために、データベースに問い合わせる。 3. シグネチャと関連するページに最近アクセスがあれば、そのページの優先度を下げて、データベースに追加する。 4. そうでなければ、ページを巡回し、そのリンクをデータベースに追加する。 上記の実装では完全なウェブの巡回はできませんが、ループに陥って巡回が止まってしまうというようなことは避けることができます。ウェブの巡回を「完了する」ということを考えるならば循環しなければならない最低の優先度をセットしておきます。これは特にイントラネットのような小規模のシステムであれば確実に必要でしょう。」 以上の回答について質問があります。 質問1: >解決策の一つはハッシュテーブルを用い、vというページにアクセスしたらhash[v]をtrueにしながら進めていく方法です。 この文章の意味はHashMapみたいなハッシュテーブルを用意するということだと思うのですが、なぜわざわざBooleanを取り入れるのでしょうか? HashSetを用意して、アクセスしたvをこのハッシュテーブルに入れておけば、それで事足りるように思えます。 仮定として、訪れることのできる全てのページはわかっているとすれば、HashMapのことも理解はできるのですが、そのようなありえない仮定はおかないと思うのです。 質問2: 1〜4で示された実装についての質問です。巡回っていうのは深さ優先探索になるのではないでしょうか? なので、子ページの優先度を下げて、キューに追加しても意味ないと思うのです。 なぜなら、深さ優先探索になるので、優先度を下げて追加しても、結局その中のものから選ばざるをえないのではないでしょうか? 質問3: >ウェブの巡回を「完了する」ということを考えるならば循環しなければならない最低の優先度をセットしておきます。これは特にイントラネットのような小規模のシステムであれば確実に必要でしょう。 これがよくわからないのですが、一体どういう意味なのでしょうか? 以上、質問が多いですが、回答お願いします。
回答: 巡回したURLを記録していって、既に巡回したURLへのリンクは無視する(巡回する候補から外す)。 そうすれば、ループは回避できます。 ハッシュテーブルは、巡回したURLを記録し、既に巡回したか否かの判断を効率的にする手段に過ぎません。 Width-firstにするか、Depth-firstにするかは、実行環境や巡回するWebの構成次第でしょう。 なにが本質的な部分で、なにが派生的な(他で代替可能な)部分なのかを考えながら、考察すると良いと思います。 お使いの計算機環境など、何らかの制約条件があるなら、それを質問に書いておくと適切な回答が得られると思います。