Japanese subtitles

← 22-36 Urank

22-36 Urank

Get Embed Code
4 Languages

Showing Revision 2 created 07/22/2014 by osawakjvta.

  1. 本レッスンの残りの目標は
    PageRankアルゴリズムを実装するために
  2. 検索エンジンのコードを修正することです
  3. 小さな問題が1つあります
  4. PageRankはGoogleの登録商標なのです
  5. たとえ動作が同じであっても
    私たちのアルゴリズムをPageRankとは呼べないので
  6. URankと名づけましょう
  7. このアルゴリズムを実装するためにまず必要な作業は
  8. リンクグラフを保持することです
  9. 私たちはページの人気度を
    リンク構造で判断しているため
  10. どのページがどのページにリンクしているのかを
    把握する必要があります
  11. 各リンクが示すページ間のつながりを
  12. グラフと見なすことができます
  13. 理論的に言えばグラフとは
    この丸で描いているノードと
  14. ノード間を結ぶエッジの集合です
  15. 私たちのエッジはページのリンクのように
    1方向に進むので
  16. 有向グラフと呼ばれます
  17. そこで私たちのWebリンク構造を表すために
  18. 有向グラフを作る必要があります
  19. ページはグラフにおけるノードです
  20. 各ページについて
  21. 自身から他のノードに出ているエッジを
    把握する必要があります
  22. そのための方法として
    ディクショナリを持つことにしましょう
  23. そのディクショナリのエントリはノードです
  24. ノードはURLすなわちページです
  25. そして各URLについて
  26. そのURLがリンクを張っている
    すべてのページのリストを保持します
  27. それではこの丸をノードA、ノードB
  28. ノードC、ノードDとしましょう
  29. ノードAのエントリはB、C、Dのリストになります
  30. ノードBのエントリは
  31. Bからはエッジが出ていないので空リストになります
  32. 例を完成させましょう
  33. Cからは1つのノードにリンクが出ています
  34. Dからはリンクが出ていません
  35. これが目標です
  36. クロールするWebページの構造を示す
    このようなグラフを作りましょう
  37. クローラでリンクを追っていくので
    この構造は把握できますね
  38. つまり私たちの目標は
    crawl_web関数を修正することです
  39. レッスン5の最後の方でも定義し直しましたね
  40. 今回はcrawl_webが
    単にインデックスを生成するだけでなく
  41. グラフも生成するようにします
  42. crawl_webの修正を行いますが
    シードページから処理を始める点は変わりません
  43. ただし生成するのはインデックスとグラフの両方です
  44. このグラフは各ノードからリンク先のページへの
    マッピングを示します
  45. レッスン5の最後の時点でのコードを確認して
  46. どのように変更するべきかを考えてみましょう
  47. これがcrawl_webの
    レッスン5が終わった時点でのコードです
  48. 復習しますがcrawl_webは
    リストtocrawlのすべてのページを追っていきます
  49. シードページseedからクロールを始めます
  50. インデックスはディクショナリとして生成します
  51. そしてtocrawlにページが残っている限り
    whileループの処理を繰り返します
  52. その時にpopでtocrawl内にあるページを
    抜き出していきます
  53. 以前にクロールしたことのないページなら
  54. そのページからコンテンツを取得して
    インデックスに追加します
  55. get_all_linksにページのコンテンツを渡して
    そのリンクをすべて取得したら
  56. その中でtocrawlに含まれていないリンクを
    tocrawlに追加します
  57. そしてこのページを
    クロール済みページのリストcrawledにappendします
  58. このcrawl_webがグラフを
    生成するように修正するには
  59. コードの大部分は変更不要です
  60. インデックスを生成するだけでなく
    グラフも生成するようにします
  61. グラフもディクショナリにします
  62. グラフは各ノードすなわち各URLについて
    そのノードから出るエッジのリストへの
  63. マッピングを示す構造となるからです
  64. ここでグラフを空のディクショナリとして生成します
  65. そして新しいページを見つけたらこのグラフに加えます
  66. さらにreturnも
    インデックスとグラフの両方を返すように変更します
  67. 小テストを行う前にもう1点変更を加えましょう
  68. get_all_linksを呼び出しているこの部分を
    変えたいと思います
  69. グラフの作成処理とリストtocrawlのどちらとも
    すべてのリンクを使うので
  70. 新しい変数outlinksを作成しましょう
  71. そしてget_all_links(content)の結果を
    outlinksに代入します
  72. こうすればoutlinksを
    tocrawlへの入力として使えますし
  73. さらにグラフの作成にも使うことができます
  74. グラフの作成を行う部分に空行を作りましたので
  75. これを小テストにしましょう
  76. グラフを更新するために必要な
    この部分のコードを書いてください