Webの巡回ソフトの設定について

Question

「Webの巡回ソフトを設計する場合、無限ループを回避するにはどのようにすれば良いですか？」

解法

まず、最初に考えるべきことはどのようにして無限ループが起こるのかということです。もっともシンプルに考えれば、ウェブをリンクのグラフと考えた時に、グラフに循環する部分があれば、そこで無限ループが起こると判断できます。

無限ループにならないようにするにはグラフの循環を検出する必要があります。解決策の一つはハッシュテーブルを用い、vというページにアクセスしたらhash[v]をtrueにしながら進めていく方法です。

これを用いて、ウェブページを幅優先探索により巡回しましょう。ウェブページを訪れる鉢に、そこからのリンクをキューに追加します。もしアクセスずみのページがあれば、無視します。

これは良い方法ですが、ウェブページvにアクセスするというのはどういうことでしょうか？ウェブページvはそのコンテンツで定義されるのか、URLで定義されるのか、どちらでしょうか？

URLで定義されるとすれば、URLのパラメータが完全に別のウェブページを示していることを確認しなければなりません。また、パラメータはそのウェブアプリケーションが認識できない、あるいは取り扱うことのできないものでも、ウェブページの内容を全く変えることなく、好き勝手に付け加えることができます。

コンテンツで定義するとすれば、あるホームページでコンテンツがランダムに生成されていると考えてください。そこは、訪れるたびに異なるページと言えるのでしょうか。そうではありませんね？

現実的には「異なる」ページを定義できそうにありません。そしてこの部分がこの問題を扱いにくくしている点です。

この問題に取り組む一つの方法としては、ページの類似性についてある程度の推定を行うことです。コンテンツとURLの両方をベースとして、あるページが他のページと十分にていると思われれば、そのページの子ページは巡回の優先度を下げるようおにします。各ページにコンテンツとURLに基づいたある種のシグネチャを取り入れます。

例えば、どのようにすればいいかを見てみましょう。

巡回する項目のリストがデータベースに保持されています。その中でもっとも優先度の高いページを選んで巡回していきます。この時、次のようにします。

1. ページを開き、内容の一部とURLをもとにシグネチャを作る。
2. 最近このシグネチャによるアクセスがあったかどうかを調べるために、データベースに問い合わせる。
3. シグネチャと関連するページに最近アクセスがあれば、そのページの優先度を下げて、データベースに追加する。
4. そうでなければ、ページを巡回し、そのリンクをデータベースに追加する。

上記の実装では完全なウェブの巡回はできませんが、ループに陥って巡回が止まってしまうというようなことは避けることができます。ウェブの巡回を「完了する」ということを考えるならば循環しなければならない最低の優先度をセットしておきます。これは特にイントラネットのような小規模のシステムであれば確実に必要でしょう。」

以上の回答について質問があります。
質問1:
＞解決策の一つはハッシュテーブルを用い、vというページにアクセスしたらhash[v]をtrueにしながら進めていく方法です。

この文章の意味はHashMap<v, Boolean>みたいなハッシュテーブルを用意するということだと思うのですが、なぜわざわざBooleanを取り入れるのでしょうか？
HashSet<v>を用意して、アクセスしたvをこのハッシュテーブルに入れておけば、それで事足りるように思えます。
仮定として、訪れることのできる全てのページはわかっているとすれば、HashMap<v, Boolean>のことも理解はできるのですが、そのようなありえない仮定はおかないと思うのです。

質問2:
1〜4で示された実装についての質問です。巡回っていうのは深さ優先探索になるのではないでしょうか？
なので、子ページの優先度を下げて、キューに追加しても意味ないと思うのです。
なぜなら、深さ優先探索になるので、優先度を下げて追加しても、結局その中のものから選ばざるをえないのではないでしょうか？

質問3:
＞ウェブの巡回を「完了する」ということを考えるならば循環しなければならない最低の優先度をセットしておきます。これは特にイントラネットのような小規模のシステムであれば確実に必要でしょう。
これがよくわからないのですが、一体どういう意味なのでしょうか？

以上、質問が多いですが、回答お願いします。

Answer 1

巡回したURLを記録していって、既に巡回したURLへのリンクは無視する（巡回する候補から外す）。
そうすれば、ループは回避できます。

ハッシュテーブルは、巡回したURLを記録し、既に巡回したか否かの判断を効率的にする手段に過ぎません。

Width-firstにするか、Depth-firstにするかは、実行環境や巡回するWebの構成次第でしょう。

なにが本質的な部分で、なにが派生的な（他で代替可能な）部分なのかを考えながら、考察すると良いと思います。

お使いの計算機環境など、何らかの制約条件があるなら、それを質問に書いておくと適切な回答が得られると思います。

Answer 2

「Webの巡回ソフトを設計する場合、無限ループを回避するにはどのようにすれば良いですか？」

難しく考えず、WebページのURLを記録しておき、「同じページを二度見ない」だけです。

ウェブページvはそのコンテンツで定義されるのか、URLで定義されるのか、どちらでしょうか？

URLの方が圧倒的に明快ですが、JSを使ったSPAなどの場合は、そうもいきませんね。

---

質問1:
なぜわざわざBooleanを取り入れるのでしょうか？

これは推測ですが、ページ構成が急に変わらないサイトなら、
一回巡回したら次からは、解析の過程をすっ飛ばして、
単純にそのリストだけ巡回した方が処理が軽い場合があります。
だから、2回目からの巡回済みチェック用のBooleanでしょうか。

ただ、このBooleanは、べつにあってもなくてもいいです。

---

質問2:
巡回っていうのは深さ優先探索になるのではないでしょうか？

いや、目的に応じて使い分けるものなので、どちらも使えます。

特定のサイトをチェックしたいだけなら深さ優先でしょうが、
たとえばソーシャルグラフ的なつながりを調べるなら幅優先です。

---

質問3:
＞ウェブの巡回を「完了する」最低の優先度をセットしておきます。
一体どういう意味なのでしょうか？

やはり推測ですが、再帰的なリンク先ページの取得には終わりがないので、
完了する条件を設定する意味でしょう。要は切り上げるフラグです。

この「優先度」も目的に応じて、自由なアルゴリズムでいいです。

「同一ドメインで、再帰レベル3まで」みたいのがそれっぽいですが、
「100ページ取得したら終わり」とか、
「1時間経ったら終わり」とかでも別にいいです。

---

まとめると、「アクセスは1秒1回まで」とかセキュリティ的なルール以外では、
アルゴリズムやデータ構造は、目的に応じて自由に決めていいです。

Comments

[退会済みユーザー]

回答ありがとうございます。
質問1に関してですが、「二回目からの巡回ずみチェック用のBoolean」というのがよくわかりませんでした。
まず、初めは当然訪れたことがないので、ハッシュテーブルには格納されていないですよね。
次に、一度訪れると、ハッシュテーブルに登録されることになると思うのですが、その時はBooleanはfalseで、そのあと訪れると、次はこのBooleanをtrueにするということでしょうか？
なぜ、このようにするかというと、解析の過程をすっ飛ばして、リストだけ巡回した方が処理が軽い場合があるからということでしょうか？
リストだけ巡回した方が処理が速くなるのはわかるのですが、そこにBoolanは必要なのですか？

[LLman]

なるほど、回答ではイメージが湧かなかったかもしれません。

まず、本文でも書いたように、Booleanは必須ではありません。
分かりやすい例では、必ず全部一回ずつ巡回なら必要ありません。

しかし、取得する順序や条件が複雑になる場合もあります。

たとえば、「商品サイトを巡回し、最初は価格やランキングだけ取得し、
条件に合うページにもう一回行って、レビューや商品画像や動画を取得する」とか。

この場合、画像や動画が重いから後の工程に飛ばしてますが、
そのとき「true」のものだけもう一回取得するとか。

これはべつにBooleanじゃなくて方法は何でもいいです。

大事なのは目的に合わせて手段を選ぶこと、
この場合は画像や動画を後回しにすることです。

[退会済みユーザー]

なるほど。ページの解析以前にBooleanがtrueかfalseで訪れるかどうかを決めるというわけですね。
その機能は巡回に必須ではないという意味で、「Booleanは必須ではない」と言われているのですね？

[LLman]

＞その機能は巡回に必須ではないという意味
その通りです。とくにコードリーディングやリファクタリングする際には、
「何が必須で、何が任意の処理か」を意識する必要があります。

[退会済みユーザー]

回答ありがとうございました。