本レッスンの残りの目標は
PageRankアルゴリズムを実装するために
検索エンジンのコードを修正することです
小さな問題が1つあります
PageRankはGoogleの登録商標なのです
たとえ動作が同じであっても
私たちのアルゴリズムをPageRankとは呼べないので
URankと名づけましょう
このアルゴリズムを実装するためにまず必要な作業は
リンクグラフを保持することです
私たちはページの人気度を
リンク構造で判断しているため
どのページがどのページにリンクしているのかを
把握する必要があります
各リンクが示すページ間のつながりを
グラフと見なすことができます
理論的に言えばグラフとは
この丸で描いているノードと
ノード間を結ぶエッジの集合です
私たちのエッジはページのリンクのように
1方向に進むので
有向グラフと呼ばれます
そこで私たちのWebリンク構造を表すために
有向グラフを作る必要があります
ページはグラフにおけるノードです
各ページについて
自身から他のノードに出ているエッジを
把握する必要があります
そのための方法として
ディクショナリを持つことにしましょう
そのディクショナリのエントリはノードです
ノードはURLすなわちページです
そして各URLについて
そのURLがリンクを張っている
すべてのページのリストを保持します
それではこの丸をノードA、ノードB
ノードC、ノードDとしましょう
ノードAのエントリはB、C、Dのリストになります
ノードBのエントリは
Bからはエッジが出ていないので空リストになります
例を完成させましょう
Cからは1つのノードにリンクが出ています
Dからはリンクが出ていません
これが目標です
クロールするWebページの構造を示す
このようなグラフを作りましょう
クローラでリンクを追っていくので
この構造は把握できますね
つまり私たちの目標は
crawl＿web関数を修正することです
レッスン5の最後の方でも定義し直しましたね
今回はcrawl＿webが
単にインデックスを生成するだけでなく
グラフも生成するようにします
crawl＿webの修正を行いますが
シードページから処理を始める点は変わりません
ただし生成するのはインデックスとグラフの両方です
このグラフは各ノードからリンク先のページへの
マッピングを示します
レッスン5の最後の時点でのコードを確認して
どのように変更するべきかを考えてみましょう
これがcrawl＿webの
レッスン5が終わった時点でのコードです
復習しますがcrawl＿webは
リストtocrawlのすべてのページを追っていきます
シードページseedからクロールを始めます
インデックスはディクショナリとして生成します
そしてtocrawlにページが残っている限り
whileループの処理を繰り返します
その時にpopでtocrawl内にあるページを
抜き出していきます
以前にクロールしたことのないページなら
そのページからコンテンツを取得して
インデックスに追加します
get＿all＿linksにページのコンテンツを渡して
そのリンクをすべて取得したら
その中でtocrawlに含まれていないリンクを
tocrawlに追加します
そしてこのページを
クロール済みページのリストcrawledにappendします
このcrawl＿webがグラフを
生成するように修正するには
コードの大部分は変更不要です
インデックスを生成するだけでなく
グラフも生成するようにします
グラフもディクショナリにします
グラフは各ノードすなわち各URLについて
そのノードから出るエッジのリストへの
マッピングを示す構造となるからです
ここでグラフを空のディクショナリとして生成します
そして新しいページを見つけたらこのグラフに加えます
さらにreturnも
インデックスとグラフの両方を返すように変更します
小テストを行う前にもう1点変更を加えましょう
get＿all＿linksを呼び出しているこの部分を
変えたいと思います
グラフの作成処理とリストtocrawlのどちらとも
すべてのリンクを使うので
新しい変数outlinksを作成しましょう
そしてget＿all＿links（content）の結果を
outlinksに代入します
こうすればoutlinksを
tocrawlへの入力として使えますし
さらにグラフの作成にも使うことができます
グラフの作成を行う部分に空行を作りましたので
これを小テストにしましょう
グラフを更新するために必要な
この部分のコードを書いてください