9回目講義資料

検索エンジン
（照合とランキング）
平成24年11月30日
アルゴリズム論 9回目
マッチング→ランキング
ランク付け
されたページ
マッチしたページ
検索要求発行
ロンドンバス時刻表
マッチング
ランキング
・・・
・・・
・・・
・
・
・
ウェブ検索には､マッチングとランキングの2段階がある｡第1(マッチング)段階終了後は、
マッチした数干～数百万ものページが残される｡第2(ランキング)段階では､これらが関連性
の高さ順にｿｰﾄされる。
Webページ番号だけから成る索引（インデックス）ファイル
1
the cat sat on
the mat
2
a
cat
dog
mat
on
sat
stood
the
while
the dog stood
on the mat
3
1
2
1
1
1
2
1
3
3
3
2
2
3
3
2
3
3
1，2，3のWebページから成るWWW
フレーズ検索“cat sat“を実現できるか？
the cat stood
while a dog sat
Webページ番号＋単語位置情報から成る
索引（インデックス）ファイル
1
the cat sat on
1 2 3 4
the mat
5
6
2
the
1
on
4
dog stood
2
3
the mat
5
6
3
the cat stood
1 2
3
while a dog sat
5 6
7
4
（ページ番号－位置情報）
a
cat
dog
mat
on
sat
stood
the
while
3-5 （ページ番号３の5番目）
1-2
3-2
2-2
3-6
1-6
2-6
1-4
2-4
1-3
3-7
2-3
3-3
1-1
1-5
2-1 2-5
3-1
3-4
マラリアに関連するWebページ
1
2
By far the most common
cause of malaria is being bitten
by an infected mosquito, but
there are also other ways to
contract the disease.
Our cause was not helped by
the poor health of the troops,
many of whom were suffering
from malaria and other tropical
diseases.
also
1-19
・・・
cause
1-6 2-2
・・・
malaria 1-8 2-19
・・・
whom
2-15
マラリアを引き起こす原因について説明しているページはどっち？
→コンピュータに判断させる方法は？
→文章の意味を理解させる人工知能を作る
→もっと簡単は方法は？
→索引ファイルだけを使う方法がある（精度は落ちるかもしれない）
タイトルと本文を持つWebページ
ブラウザー表示
1
2
my cat
3
my dog
the dog stood
on the mat
the cat sat on
the mat
my pets
the cat stood
while a dog sat
HTMLライクな表示：＜＞メタワード，タグ
1
<title>
my cat
</title>
<body>
the cat sat on the mat
</body>
2
<title>
my dog
</title>
<body>
the dog stood on the
mat
</body>
3
<title>
my pets
</title>
<body>
the cat stood
while a dog sat
</body>
タグと文字を含んだインデックスファイル
タイトルにdogを含むページを検索したい
a
cat
dog
mat
my
on
pets
sat
stood
the
while
</body> <
<body>
ti
</title>
tl
<title>
3-10
1-3 1-7 3-7
2-3 2-7 3-11
1-11 2-11
1-2 2-2 3-2
1-9 2-9
3-3
1-8 3-12
2-8 3-8
1-6 1-10 2-6 2-10 3-6
3-9
1-12 2-12 3-13
1-5 2-5 3-5
1-4 2-4 3-4
<
1-1 2-1 3-1
ti
e
dog: 2-3 2-7tl< 3-11
eti
E
<title>: n1-1 2-1
3-1
tl
Ee
d
</title>: >1-4 2-4
3-4
n
dE
>n
Webページランキング
（Googleの基本的アイデア）
ハイパーリンクトリック
アーニーのスクランブル
エッグレシピ
バートのスクランブル
エッグレシピ
ボウルで4個の卵と
塩胡椒少々を混ぜる・・・
まず大さじ1杯のバターを
溶かす・・・
アーニーのレシピ
はよい
私はバートのレシピが
本当に気に入った
バートのレシピは
すばらしい
バートのレシピは
とてもいい
パートのページを参照しているリンクが3つ
アーニーのページを参照しているリンクが1つ
→バートのページ評価＞アーニーのページ評価
オーソリティトリック
アーニーのスクランブル
エッグレシピ
バートのスクランブル
エッグレシピ
ボウルで4個の卵と
塩胡椒少々を混ぜる・・・
まず大さじ1杯のバターを
溶かす・・・
ジョン・マコーミックの
ホームページ
アリス・ウォーターズの
ホームページ
私は一度アーニーのレシピ
を試してみたが、決して悪い
ものではなかった。
バートのレシピは、間違いなく
最良のレシピの１つだ。
ジョン・マコーミック：コンピュータ科学者
アリス・ウォーターズ：有名なシェフ
→バートのページ評価＞アーニーのページ評価
でも，コンピュータはどちらが権威をもつページなのか分からない
オーソリティトリックの近似計算
アーニーのスクランブル
エッグレシピ
バートのスクランブル
エッグレシピ
ボウルで4個の卵と
塩胡椒少々を混ぜる・・・
まず大さじ1杯のバターを
溶かす・・・
2
ジョン・マコーミックの
ホームページ
私は一度アーニーのレシピ
を試してみたが、決して悪い
ものではなかった。
1
1
100
アリス・ウォーターズの
ホームページ
バートのレシピは、間違いなく
最良のレシピの１つだ。
100
2
1
1
1
1
・・・100pages・・・
1
1
1
1
循環参照問題
A
C
B
D
E
ハイパーリンクの循環参照の例．A､B､Ｅページは､Ａからスタートして､Ｂ､続いてＥに移動し，
最後に出発点であるＡに戻ってこれてしまうので循環参照を形成している。
A
C
1
B
2
A
2
D
1
E
2
C
1
B
4
4
D
1
E
循環参照によって起きる問題｡
Ａ､B､Ｅのスコアはいつも修正が必要になり､無限に大きくなっていってしまう。
4
ランダムサーファーモデル
B
C
A
濃い色：サーファーが訪れたページ
破線の矢印：ランダムな再スタート
サーファーは､Ａからスタートし､2回のランダムな再スタートをはさんで，
ランダムにハイパーリンクを選択している。
D
ランダムサーファーモデルの
シミュレーション
B
109
1000回
（訪問回数）
16
74
55
58
13
C
46
55
32
17
21
A 118
126
101
15
144 D
B
100万回
（訪問割合）
10%
7%
4%
2%
5%
4%
2%
C
4%
4%
2%
2%
A 13%
14%
10%
2%
15% D
サーファーオーソリティ(1)
アーニーのスクランブル
エッグレシピ
バートのスクランブル
エッグレシピ
1%
28%
ジョン・マコーミックの
ホームページ
アリス・ウォーターズの
ホームページ
1%
0.4%
0.4%
0.4%
32%
0.4%
0.4%
0.4%
・・・100pages・・・
0.4%
0.4%
0.4%
0.4%
サーファーオーソリティ(2)
A
B
33%
C
31%
D
3%
E
3%
30%

Download Report