WEBVTT

00:00:00.100 --> 00:00:03.870
本レッスンの残りの目標は
PageRankアルゴリズムを実装するために

00:00:03.870 --> 00:00:06.430
検索エンジンのコードを修正することです

00:00:06.430 --> 00:00:08.770
小さな問題が1つあります

00:00:08.770 --> 00:00:11.370
PageRankはGoogleの登録商標なのです

00:00:11.370 --> 00:00:15.940
たとえ動作が同じであっても
私たちのアルゴリズムをPageRankとは呼べないので

00:00:15.940 --> 00:00:19.150
URankと名づけましょう

00:00:19.150 --> 00:00:22.920
このアルゴリズムを実装するためにまず必要な作業は

00:00:22.920 --> 00:00:25.690
リンクグラフを保持することです

00:00:25.690 --> 00:00:29.520
私たちはページの人気度を
リンク構造で判断しているため

00:00:29.520 --> 00:00:34.860
どのページがどのページにリンクしているのかを
把握する必要があります

00:00:34.860 --> 00:00:38.500
各リンクが示すページ間のつながりを

00:00:38.500 --> 00:00:41.740
グラフと見なすことができます

00:00:41.740 --> 00:00:45.870
理論的に言えばグラフとは
この丸で描いているノードと

00:00:45.870 --> 00:00:48.910
ノード間を結ぶエッジの集合です

00:00:49.930 --> 00:00:53.850
私たちのエッジはページのリンクのように
1方向に進むので

00:00:53.850 --> 00:00:56.080
有向グラフと呼ばれます

00:00:56.080 --> 00:00:59.720
そこで私たちのWebリンク構造を表すために

00:00:59.720 --> 00:01:01.760
有向グラフを作る必要があります

00:01:01.760 --> 00:01:04.660
ページはグラフにおけるノードです

00:01:04.660 --> 00:01:06.000
各ページについて

00:01:06.000 --> 00:01:11.300
自身から他のノードに出ているエッジを
把握する必要があります

00:01:11.300 --> 00:01:15.530
そのための方法として
ディクショナリを持つことにしましょう

00:01:16.330 --> 00:01:20.040
そのディクショナリのエントリはノードです

00:01:20.040 --> 00:01:22.280
ノードはURLすなわちページです

00:01:22.280 --> 00:01:24.200
そして各URLについて

00:01:24.200 --> 00:01:27.320
そのURLがリンクを張っている
すべてのページのリストを保持します

00:01:27.320 --> 00:01:29.720
それではこの丸をノードA、ノードB

00:01:29.720 --> 00:01:32.420
ノードC、ノードDとしましょう

00:01:32.420 --> 00:01:35.790
ノードAのエントリはB、C、Dのリストになります

00:01:35.790 --> 00:01:38.560
ノードBのエントリは

00:01:38.560 --> 00:01:42.930
Bからはエッジが出ていないので空リストになります

00:01:42.930 --> 00:01:45.270
例を完成させましょう

00:01:45.270 --> 00:01:48.600
Cからは1つのノードにリンクが出ています

00:01:48.600 --> 00:01:51.910
Dからはリンクが出ていません

00:01:52.560 --> 00:01:53.480
これが目標です

00:01:53.480 --> 00:01:58.580
クロールするWebページの構造を示す
このようなグラフを作りましょう

00:01:58.580 --> 00:02:02.020
クローラでリンクを追っていくので
この構造は把握できますね

00:02:02.220 --> 00:02:06.590
つまり私たちの目標は
crawl＿web関数を修正することです

00:02:06.590 --> 00:02:10.130
レッスン5の最後の方でも定義し直しましたね

00:02:10.130 --> 00:02:13.330
今回はcrawl＿webが
単にインデックスを生成するだけでなく

00:02:13.330 --> 00:02:15.560
グラフも生成するようにします

00:02:15.560 --> 00:02:19.870
crawl＿webの修正を行いますが
シードページから処理を始める点は変わりません

00:02:19.870 --> 00:02:24.270
ただし生成するのはインデックスとグラフの両方です

00:02:24.270 --> 00:02:29.410
このグラフは各ノードからリンク先のページへの
マッピングを示します

00:02:29.410 --> 00:02:32.280
レッスン5の最後の時点でのコードを確認して

00:02:32.280 --> 00:02:34.180
どのように変更するべきかを考えてみましょう

00:02:34.200 --> 00:02:37.590
これがcrawl＿webの
レッスン5が終わった時点でのコードです

00:02:37.590 --> 00:02:43.260
復習しますがcrawl＿webは
リストtocrawlのすべてのページを追っていきます

00:02:43.260 --> 00:02:45.190
シードページseedからクロールを始めます

00:02:45.190 --> 00:02:47.530
インデックスはディクショナリとして生成します

00:02:47.530 --> 00:02:51.300
そしてtocrawlにページが残っている限り
whileループの処理を繰り返します

00:02:51.300 --> 00:02:55.500
その時にpopでtocrawl内にあるページを
抜き出していきます

00:02:55.500 --> 00:02:57.640
以前にクロールしたことのないページなら

00:02:57.640 --> 00:03:00.640
そのページからコンテンツを取得して
インデックスに追加します

00:03:00.640 --> 00:03:04.780
get＿all＿linksにページのコンテンツを渡して
そのリンクをすべて取得したら

00:03:04.780 --> 00:03:08.320
その中でtocrawlに含まれていないリンクを
tocrawlに追加します

00:03:08.320 --> 00:03:11.790
そしてこのページを
クロール済みページのリストcrawledにappendします

00:03:11.790 --> 00:03:15.130
このcrawl＿webがグラフを
生成するように修正するには

00:03:15.130 --> 00:03:16.890
コードの大部分は変更不要です

00:03:16.890 --> 00:03:21.500
インデックスを生成するだけでなく
グラフも生成するようにします

00:03:21.500 --> 00:03:23.500
グラフもディクショナリにします

00:03:23.500 --> 00:03:28.770
グラフは各ノードすなわち各URLについて
そのノードから出るエッジのリストへの

00:03:28.770 --> 00:03:30.970
マッピングを示す構造となるからです

00:03:30.970 --> 00:03:34.540
ここでグラフを空のディクショナリとして生成します

00:03:34.540 --> 00:03:37.310
そして新しいページを見つけたらこのグラフに加えます

00:03:37.310 --> 00:03:42.220
さらにreturnも
インデックスとグラフの両方を返すように変更します

00:03:42.220 --> 00:03:45.620
小テストを行う前にもう1点変更を加えましょう

00:03:45.620 --> 00:03:49.820
get＿all＿linksを呼び出しているこの部分を
変えたいと思います

00:03:49.820 --> 00:03:54.660
グラフの作成処理とリストtocrawlのどちらとも
すべてのリンクを使うので

00:03:54.660 --> 00:03:57.000
新しい変数outlinksを作成しましょう

00:03:57.000 --> 00:04:00.400
そしてget＿all＿links（content）の結果を
outlinksに代入します

00:04:00.400 --> 00:04:04.610
こうすればoutlinksを
tocrawlへの入力として使えますし

00:04:04.610 --> 00:04:08.080
さらにグラフの作成にも使うことができます

00:04:08.080 --> 00:04:12.680
グラフの作成を行う部分に空行を作りましたので

00:04:12.680 --> 00:04:14.780
これを小テストにしましょう

00:04:14.780 --> 00:04:18.589
グラフを更新するために必要な
この部分のコードを書いてください