最近、面接の準備として本を読んでいて、次の質問に出くわしました。
あなたのクローラーが無限のサブグラフを生成するハニー ポットに遭遇した場合、あなたはどうしますか?
このqnに対するいくつかの解決策を得たいと思っていました。個人的には、継続的なトラバースを防ぐために、何らかの形で深さを制限した検索を行います。または、何らかの形の機械学習を使用してパターンを検出することもできます。考え？
3346 次
2 に答える
7
最も一般的な無限サブグラフは、リンクの深さによって妨げられます。したがって、URL の初期セットを取得し、それぞれから有限の深さまでトラバースします。トラバースの深さを制限しながら、いくつかのヒューリスティックを使用して、Web ページの特性に従って動的に調整することができます。詳細については、ここなどを参照してください。
別のオプションは、ある種のパターン マッチングを試すことです。しかし、サブグラフを生成するアルゴリズムによっては、これは非常に (非常に) 難しい作業になります。これはまた、少なくともかなり高価な操作になります。
インタビューの質問 (無限ループの検出について):
彼らがこの質問をした場合、誰かが停止問題への言及を聞きたがっています
アラン・チューリングは 1936 年に、考えられるすべてのプログラムと入力の組み合わせに対して停止問題を解決する一般的なアルゴリズムは存在しないことを証明しました。
于 2011-07-21T18:16:54.783 に答える
4
取得するページ数を制限できます。もちろん、これには問題があります..サイトが本当に巨大な場合はどうなりますか? ウィキペディアは無限ですか？:)
より良い方法は、リンクしている外部サイトの数と、それらがリンクしている個別のページの数に基づいてしきい値を設定することです。数値が大きいほど、しきい値が大きくなります。これにより、相互にリンクする無限ハニーポットのカップルの問題を解決できます。
于 2011-07-21T18:09:17.127 に答える