質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

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

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 1,065
退会済みユーザー

退会済みユーザー

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+1

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

0

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

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

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

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


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

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

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


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

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

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


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

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

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

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


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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2016/09/17 20:36

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

    キャンセル

  • 2016/09/17 20:41

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

    キャンセル

  • 2016/09/17 20:43

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る