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

2
00:00:03,870 --> 00:00:06,430
検索エンジンのコードを修正することです

3
00:00:06,430 --> 00:00:08,770
小さな問題が1つあります

4
00:00:08,770 --> 00:00:11,370
PageRankはGoogleの登録商標なのです

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

6
00:00:15,940 --> 00:00:19,150
URankと名づけましょう

7
00:00:19,150 --> 00:00:22,920
このアルゴリズムを実装するためにまず必要な作業は

8
00:00:22,920 --> 00:00:25,690
リンクグラフを保持することです

9
00:00:25,690 --> 00:00:29,520
私たちはページの人気度を
リンク構造で判断しているため

10
00:00:29,520 --> 00:00:34,860
どのページがどのページにリンクしているのかを
把握する必要があります

11
00:00:34,860 --> 00:00:38,500
各リンクが示すページ間のつながりを

12
00:00:38,500 --> 00:00:41,740
グラフと見なすことができます

13
00:00:41,740 --> 00:00:45,870
理論的に言えばグラフとは
この丸で描いているノードと

14
00:00:45,870 --> 00:00:48,910
ノード間を結ぶエッジの集合です

15
00:00:49,930 --> 00:00:53,850
私たちのエッジはページのリンクのように
1方向に進むので

16
00:00:53,850 --> 00:00:56,080
有向グラフと呼ばれます

17
00:00:56,080 --> 00:00:59,720
そこで私たちのWebリンク構造を表すために

18
00:00:59,720 --> 00:01:01,760
有向グラフを作る必要があります

19
00:01:01,760 --> 00:01:04,660
ページはグラフにおけるノードです

20
00:01:04,660 --> 00:01:06,000
各ページについて

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

22
00:01:11,300 --> 00:01:15,530
そのための方法として
ディクショナリを持つことにしましょう

23
00:01:16,330 --> 00:01:20,040
そのディクショナリのエントリはノードです

24
00:01:20,040 --> 00:01:22,280
ノードはURLすなわちページです

25
00:01:22,280 --> 00:01:24,200
そして各URLについて

26
00:01:24,200 --> 00:01:27,320
そのURLがリンクを張っている
すべてのページのリストを保持します

27
00:01:27,320 --> 00:01:29,720
それではこの丸をノードA、ノードB

28
00:01:29,720 --> 00:01:32,420
ノードC、ノードDとしましょう

29
00:01:32,420 --> 00:01:35,790
ノードAのエントリはB、C、Dのリストになります

30
00:01:35,790 --> 00:01:38,560
ノードBのエントリは

31
00:01:38,560 --> 00:01:42,930
Bからはエッジが出ていないので空リストになります

32
00:01:42,930 --> 00:01:45,270
例を完成させましょう

33
00:01:45,270 --> 00:01:48,600
Cからは1つのノードにリンクが出ています

34
00:01:48,600 --> 00:01:51,910
Dからはリンクが出ていません

35
00:01:52,560 --> 00:01:53,480
これが目標です

36
00:01:53,480 --> 00:01:58,580
クロールするWebページの構造を示す
このようなグラフを作りましょう

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

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

39
00:02:06,590 --> 00:02:10,130
レッスン5の最後の方でも定義し直しましたね

40
00:02:10,130 --> 00:02:13,330
今回はcrawl＿webが
単にインデックスを生成するだけでなく

41
00:02:13,330 --> 00:02:15,560
グラフも生成するようにします

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

43
00:02:19,870 --> 00:02:24,270
ただし生成するのはインデックスとグラフの両方です

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

45
00:02:29,410 --> 00:02:32,280
レッスン5の最後の時点でのコードを確認して

46
00:02:32,280 --> 00:02:34,180
どのように変更するべきかを考えてみましょう

47
00:02:34,200 --> 00:02:37,590
これがcrawl＿webの
レッスン5が終わった時点でのコードです

48
00:02:37,590 --> 00:02:43,260
復習しますがcrawl＿webは
リストtocrawlのすべてのページを追っていきます

49
00:02:43,260 --> 00:02:45,190
シードページseedからクロールを始めます

50
00:02:45,190 --> 00:02:47,530
インデックスはディクショナリとして生成します

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

52
00:02:51,300 --> 00:02:55,500
その時にpopでtocrawl内にあるページを
抜き出していきます

53
00:02:55,500 --> 00:02:57,640
以前にクロールしたことのないページなら

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

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

56
00:03:04,780 --> 00:03:08,320
その中でtocrawlに含まれていないリンクを
tocrawlに追加します

57
00:03:08,320 --> 00:03:11,790
そしてこのページを
クロール済みページのリストcrawledにappendします

58
00:03:11,790 --> 00:03:15,130
このcrawl＿webがグラフを
生成するように修正するには

59
00:03:15,130 --> 00:03:16,890
コードの大部分は変更不要です

60
00:03:16,890 --> 00:03:21,500
インデックスを生成するだけでなく
グラフも生成するようにします

61
00:03:21,500 --> 00:03:23,500
グラフもディクショナリにします

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

63
00:03:28,770 --> 00:03:30,970
マッピングを示す構造となるからです

64
00:03:30,970 --> 00:03:34,540
ここでグラフを空のディクショナリとして生成します

65
00:03:34,540 --> 00:03:37,310
そして新しいページを見つけたらこのグラフに加えます

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

67
00:03:42,220 --> 00:03:45,620
小テストを行う前にもう1点変更を加えましょう

68
00:03:45,620 --> 00:03:49,820
get＿all＿linksを呼び出しているこの部分を
変えたいと思います

69
00:03:49,820 --> 00:03:54,660
グラフの作成処理とリストtocrawlのどちらとも
すべてのリンクを使うので

70
00:03:54,660 --> 00:03:57,000
新しい変数outlinksを作成しましょう

71
00:03:57,000 --> 00:04:00,400
そしてget＿all＿links（content）の結果を
outlinksに代入します

72
00:04:00,400 --> 00:04:04,610
こうすればoutlinksを
tocrawlへの入力として使えますし

73
00:04:04,610 --> 00:04:08,080
さらにグラフの作成にも使うことができます

74
00:04:08,080 --> 00:04:12,680
グラフの作成を行う部分に空行を作りましたので

75
00:04:12,680 --> 00:04:14,780
これを小テストにしましょう

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