Document

検索エンジンに関して
The Anatomy of a Large-Scale Hypertextual Web
Search Engine
2003/05/27
M1 藤本 浩史
発表の流れ
1.
2.
3.
4.
研究の概要
検索エンジンの仕組み
PageRank
今後の展望
1.研究の概要
• 検索エンジン
– 分散Indexer(インデクサ)の実装
2.検索エンジンの仕組み
•
検索エンジンの構造
– Crawler
– Indexer
– Searcher
2.検索エンジンの仕組み
~Crawler~
•
Crawlerとは?
– WWW上を自動的に巡回してWebページを
収集する検索ロボットプログラム
2.検索エンジンの仕組み
~Crawler~
•
Crawlerの挙動
1. 「Crawler」がWWWからドキュメントを
収集し「Store Server」に渡す
2. 「Store Server」はページごとに一意の
{docID}を割り当て、圧縮してRepository
に保存
2.検索エンジンの仕組み
~Crawler~
Crawler
Crawler
WEB
Store Server
docID
Crawler
Compress
Crawler
Repository
2.検索エンジンの仕組み
~Crawler~
• Repository Data Structure
docID ecode urllen pagelen url
page
– docID: Webページ(URL)に対する一意
のID
– page : 実際のWebページコンテンツ
2.検索エンジンの仕組み
•
検索エンジンの構造
– Crawler
– Indexer
– Searcher
2.検索エンジンの仕組み
~Indexer~
• Indexer
– Crawlerが収集したWebページを解析し検
索に使用するためのインデックスを生成
2.検索エンジンの仕組み
~Indexer~
•
Indexerの挙動
1.
2.
3.
4.
形態素解析
Forward Index(正引き索引)作成
Inverted Index(逆引き索引)作成
アンカー(リンク)切り出し
2.検索エンジンの仕組み
~Indexer~
• 形態素解析
– 自然文から品詞ごとの単語を切り出す
> 日本語では辞書を使用
2.検索エンジンの仕組み
~Indexer~
•
Forward Index
1. ページに含まれる単語を{wordID}に置き
換える
2. {docID}に{wordID}リストを割り当てる
{docID}
Google
{wordID}
Web
Images
Groups
Directory
{Null}
{params}
・・・・・・
・・・・・・
・・・・・・
・・・・・・
2.検索エンジンの仕組み
~Indexer~
• Inverted Index
– Forward Indexを元に{wordID}⇒{docID}の
インデックスを作成する
– 検索で使用されるのはこのインデックス
{wordID}
Web
{docID}
Google
Yahoo!
InfoSeek
{params}
・・・・・・
・・・・・・
・・・・・・
2.検索エンジンの仕組み
~Indexer~
• アンカー切り出し
– Webページからリンクを切り出す
– URLを相対リンクから絶対リンクへ
2.検索エンジンの仕組み
~Indexer~
• Indexerの構成
– プログラム
> Indexer:Forward Indexを作成
> Sorter :Inverted Indexを作成
– データベース
> Lexicon:辞書(単語とwordIDをマップ)
> Barrels:Indexを格納するデータベース
2.検索エンジンの仕組み
~Indexerの構成~
• 形態素解析
decompress
Repository
docID
Lexicon 辞書
分散検索エンジン
分散 / 検索 / エンジン
Webページに含まれる文書を、辞書を用いて単語に分解
2.検索エンジンの仕組み
~Indexerの構成~
• Forward Indexの作成
wordID{エンジン}
wordID{検索}
wordID{分散}
docID
Indexer
{docID} {wordID}
docID
{分散}
{検索}
{エンジン}
{Null}
Lexicon
Forward Index
エンジン
検索
分散
Barrels
{params}
・・・・・・
・・・・・・
・・・・・・
2.検索エンジンの仕組み
~Indexerの構成~
• Inverted Indexの作成
{wordID}
hoge
Barrels
{docID}
Google
Yahoo!
InfoSeek
{params}
・・・・・・
・・・・・・
・・・・・・
Inverted Index
Forward Index
Sorter
Lexicon 辞書
2.検索エンジンの仕組み
~Indexerの構成~
• アンカーの切り出し
docID
Indexer
decompress
<a>Link</a>
Anchor
Repository
このリンクを元にCrawlerが巡回
2.検索エンジンの仕組み
• Indexerの構成
decompress
Repository
Indexer
Forward Index
Lexicon
Barrels
Inverted Index
Sorter
2.検索エンジンの仕組み
•
検索エンジンの構造
– Crawler
– Indexer
– Searcher
2.検索エンジンの仕組み
• Searcher
– Webサーバー上で動作
– ユーザーからの検索キーを受け付ける
– Indexerが生成したインデックスを参照し
て検索キーにマッチする検索結果を返却
2.検索エンジンの仕組み
~Searcher~
検索キー
Searcher
Barrels
Inverted Index
2.検索エンジンの仕組み
~Searcher~
• 検索アルゴリズム
– テキストマッチ
– タグ重み付け
– キーワード頻出度
– キーワードの出現位置
– キーワード近接度
– etc.
2.検索エンジンの仕組み
~Searcher~
• テキストマッチ
– 検索キーと一致するテキストが文書内に含
まれている
検索キー:hoge
{wordID}
hoge
{docID}
Google
Yahoo!
InfoSeek
{params}
・・・・・・
・・・・・・
・・・・・・
【Inverted Index】
2.検索エンジンの仕組み
~Searcher~
• タグ重み付け
– HTMLタグの種類により重みをつける
<EX>Namazu
タグの種類 タグの重み
H1
8
H2
7
A
4
STRONG
2
EM
2
発表の流れ
1. 研究の概要
2. 検索エンジンの仕組み
•
•
•
Crawler
Indexer
Searcher
3. PageRankの仕組み
4. 今後の展望
3.PageRankの仕組み
• 質の高い検索結果を返すには?
– サイトの質を内容から判別することは困難
• (Yahoo!のように人間が判断)
– 定量的に解析できる手法を
– ジャンクサイトを排除
• 従来の検索アルゴリズムを逆手に取る
3.PageRankの仕組み
• 基本概念
– 「多くの良質なページからリンクされてい
るページは、やはり良質なページである」
– Googleによって提唱
3.PageRankの仕組み
~概念~
•
PageRankの測り方
1. 被リンク数
2. PageRankの高いページからのリンク
(Yahoo!など)
3. リンク元のリンク数
3.PageRankの仕組み
~概念~
• PageRankの概念図
50
100
50
50
リンク
リンク
リンク
50
12
4
リンク
リンク
リンク
4
4
54
リンク
リンク
27
27
3.PageRankの仕組み
~モデリング~
•
Random Walker on the Web
– PageRankのモデリング
1.
2.
3.
4.
ネットサーファーを考える
Web上のリンクをランダムに進んでいく
決して前のページには戻らない
時折全く関係のないページへ飛ぶ
ネットサーファーが、あるサイトを訪れる確率がPageRank
3.PageRankの仕組み
~モデリング~
• 突然無関係なページへ遷移
3.PageRankの仕組み
~簡単な例~
• PageRankの計算方法
ID=1
– 閉じたWWWを考える
– 3ページで構成
ID=2
ID=3
3.PageRankの仕組み
~簡単な例~
• PageRankの計算方法
(i  jへのリンクが存在 )
1 / N i Ai , j  
0(i  jへのリンクが存在しな い) N i : iから出るリンク数
ID=1
1/2
1/2 1
ID=2
1/2
1/2
隣接行列
ID=3
0, ½, ½
A =
½, 0, ½
1, 0, 0
1
 
P0   0 
0
 
3.PageRankの仕組み
~計算手法~
• 一般化
P1  A P0
T
P0 ( N次) : 初期状態
AT ( N  N次) : 確率推移行列
(隣接行列の転置)
T
A
現在の存在確率に をかけると
1ステップ先の存在確率が求まる
3.PageRankの仕組み
~計算手法~
• 一般化
Pn  ( AT ) n  P0
P0 : 初期状態
AT : 確率推移行列
(隣接行列の転置)



P0  



p1 

 
 

pN 

n  における Pn の定常状態の値がPageRank
3.PageRankの仕組み
~計算手法~
• PageRankの計算方法
– 固有値、固有ベクトル
A x  x
T
固有値: 1 , 2 ,...,N
固有ベクトル: x1 , x2 ,..., xN
3.PageRankの仕組み
~計算手法~
• PageRankの計算方法
Pn  ( AT ) n  P0
xi (1  i  N )は各々独立なので以下のように書ける
P0  c1 x1  c2 x2  ... cN xN (ci : 定数)
 c1 ( A ) x1  ... cN ( A ) xN
T n
T n
3.PageRankの仕組み
~計算手法~
• 続き(1)
定義より
A xi  i xi (i : 1  i  N )
T
Pn  c1 (1 ) x1  ... cN (N ) xN
n
n
(ただし | 1 || 2 | .... | N |)
Pnは発散せず、また0に 収束することもない
3.PageRankの仕組み
~計算手法~
• 続き(2)
Pn  c1 (1 ) x1  ... cN (N ) xN
n
Pn  c1 x1
n
(ただし | 1 || 2 | .... | N |)
PageRankは
最大固有値の固有ベクトルを正規化したものに一致
3.PageRankの仕組み
~計算手法~
• 何が言えるか?
Pn  ( AT ) n  P0
O( N 3  n) : n  
Pn  c1 x1
O( N 2 ) : Gaussの消去法
PageRankを求めるための計算量を大幅に軽減できる
3.PageRankの仕組み
• 現実問題
– 全てのWebサイトがリンクでつながってい
るわけではない
– Dangling Linkの存在
3.PageRankの仕組み
• 解決法
– ネットサーファーは時折全く関係のない
ページへ飛ぶ
3.PageRankの仕組み
• マルコフ連鎖におけるエルゴード性
– 遷移によって任意の状態から全ての状態へ
移ることができればエルゴード的であるこ
とが言える
– つまり、ネットサーファーの気まぐれがエ
ルゴード性をもたらす
先ほど計算した手法を現実に適用できる
3.PageRank
• Googleの例(1)
– ネットサーファーが「無関係なページへ飛
ぶ確率」は0.15/1.15(13%程度)
p
p
存在する Webページの数を Nとすると
p
p
あるページに遷移する 確率は
0.15
p
N
1.15
3.PageRank
• Googleの例(2)
– 逆に、全く関係のないページから遷移して
くる確率も0.15/1.15(13%程度)
p
p
p
p
0.15
N
1.15
3.PageRankの仕組み
• PageRankの計算方法
PR( A) 
(1  d )  d ( PR(T1 ) / C (T1 )  ...  PR(Tn ) / C (Tn ))
– PR:ページランク
– C:ページから出て行くリンク数
– d:リンクを辿って次の状態へ遷移す
る確率
3.PageRankの仕組み
~まとめ~
• 定量的に解析可能
– PageRankが一意に定まる
• 現実的な計算量でPageRankを算出
– Googleでは7500万ページを5時間
3.今後の展望
• Indexerの並列分散化
– Linuxクラスタによって低コストで高速化
– 汎用的なフレームワークとして実装
• 検索アルゴリズム
– PageRankを含めた優れた検索アルゴリズ
ムの模索
3.今後の展望
• Indexerの並列分散化と汎用化
Rule
Indexer
Index
Anchor
Repository
Indexer
Index
Index
Anchor
Repository
Repository
Indexer
Index
Anchor
Anchor