本レッスンの残りの目標は
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への入力として使えますし

さらにグラフの作成にも使うことができます

グラフの作成を行う部分に空行を作りましたので

これを小テストにしましょう

グラフを更新するために必要な
この部分のコードを書いてください