Download presentation
Presentation is loading. Please wait.
1
検索エンジンに関して The Anatomy of a Large-Scale Hypertextual Web Search Engine
2003/05/27 M1 藤本 浩史
2
発表の流れ 研究の概要 検索エンジンの仕組み PageRank 今後の展望
3
１．研究の概要 検索エンジン 分散Indexer（インデクサ）の実装
4
２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher
5
２．検索エンジンの仕組み ～Crawler～
WWW上を自動的に巡回してWebページを収集する検索ロボットプログラム
6
２．検索エンジンの仕組み ～Crawler～
「Crawler」がWWWからドキュメントを 収集し「Store Server」に渡す 「Store Server」はページごとに一意の｛docID｝を割り当て、圧縮してRepositoryに保存
7
２．検索エンジンの仕組み ～Crawler～
Store Server Crawler docID WEB Crawler Crawler Compress Crawler Repository
8
２．検索エンジンの仕組み ～Crawler～
Repository Data Structure docID ecode urllen pagelen url page docID: Webページ（URL）に対する一意のID page : 実際のWebページコンテンツ
9
２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher
10
２．検索エンジンの仕組み ～Indexer～
Crawlerが収集したWebページを解析し検索に使用するためのインデックスを生成
11
２．検索エンジンの仕組み ～Indexer～
形態素解析 Forward Index（正引き索引）作成 Inverted Index（逆引き索引）作成 アンカー（リンク）切り出し
12
２．検索エンジンの仕組み ～Indexer～
形態素解析 自然文から品詞ごとの単語を切り出す > 日本語では辞書を使用
13
２．検索エンジンの仕組み ～Indexer～
Forward Index ページに含まれる単語を{wordID}に置き換える {docID}に{wordID}リストを割り当てる Google Web Images Groups Directory {Null} ・・・・・・ {docID} {wordID} {params}
14
２．検索エンジンの仕組み ～Indexer～
Inverted Index Forward Indexを元に{wordID}⇒{docID}のインデックスを作成する 検索で使用されるのはこのインデックス Google Web ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek
15
２．検索エンジンの仕組み ～Indexer～
アンカー切り出し Webページからリンクを切り出す URLを相対リンクから絶対リンクへ
16
２．検索エンジンの仕組み ～Indexer～
プログラム > Indexer：Forward Indexを作成 > Sorter ：Inverted Indexを作成 データベース > Lexicon：辞書（単語とwordIDをマップ） > Barrels：Indexを格納するデータベース
17
２．検索エンジンの仕組み ～Indexerの構成～
形態素解析 decompress Repository Lexicon 辞書 docID 分散検索エンジン 分散 / 検索 / エンジン Webページに含まれる文書を、辞書を用いて単語に分解
18
２．検索エンジンの仕組み ～Indexerの構成～
Forward Indexの作成 docID wordID{エンジン} wordID{検索} wordID{分散} Indexer docID ｛分散｝ ｛検索｝ ｛エンジン｝ ｛Null｝ ・・・・・・ {docID} {wordID} {params} Lexicon この後にForward Indexのデータ構造を入れる Forward Index エンジン 検索 分散 Barrels
19
２．検索エンジンの仕組み ～Indexerの構成～
Inverted Indexの作成 Google hoge ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek Barrels Inverted Index Forward Index Sorter Lexicon 辞書
20
２．検索エンジンの仕組み ～Indexerの構成～
アンカーの切り出し docID Indexer <a>Link</a> decompress Anchor Repository このリンクを元にCrawlerが巡回
21
２．検索エンジンの仕組み Indexerの構成 decompress Repository Indexer Forward Index
Barrels Lexicon Inverted Index Sorter
22
２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher
23
２．検索エンジンの仕組み Searcher Webサーバー上で動作 ユーザーからの検索キーを受け付ける
Indexerが生成したインデックスを参照して検索キーにマッチする検索結果を返却
24
２．検索エンジンの仕組み ～Searcher～
検索キー Searcher Barrels Inverted Index
25
２．検索エンジンの仕組み ～Searcher～
検索アルゴリズム テキストマッチ タグ重み付け キーワード頻出度 キーワードの出現位置 キーワード近接度 etc.
26
２．検索エンジンの仕組み ～Searcher～
テキストマッチ 検索キーと一致するテキストが文書内に含まれている Searcherの実際の挙動を説明 Google hoge ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek 検索キー：hoge 【Inverted Index】
27
２．検索エンジンの仕組み ～Searcher～
タグ重み付け HTMLタグの種類により重みをつける ＜EX>Namazu タグの種類 タグの重み H1 8 A 4 STRONG 2 EM H2 7
28
発表の流れ 研究の概要 検索エンジンの仕組み Crawler Indexer Searcher PageRankの仕組み 今後の展望
29
３．PageRankの仕組み 質の高い検索結果を返すには？ サイトの質を内容から判別することは困難 定量的に解析できる手法を
（Yahoo!のように人間が判断） 定量的に解析できる手法を ジャンクサイトを排除 従来の検索アルゴリズムを逆手に取る
30
３．PageRankの仕組み 基本概念 「多くの良質なページからリンクされているページは、やはり良質なページである」
Googleによって提唱
31
３．PageRankの仕組み ～概念～ PageRankの測り方 被リンク数 PageRankの高いページからのリンク （Yahoo!など）
リンク元のリンク数
32
３．PageRankの仕組み ～概念～ PageRankの概念図 50 100 50 50 54 12 27 4 4 27 4 リンク
33
３．PageRankの仕組み ～モデリング～
Random Walker on the Web PageRankのモデリング ネットサーファーを考える Web上のリンクをランダムに進んでいく 決して前のページには戻らない 時折全く関係のないページへ飛ぶ ネットサーファーが、あるサイトを訪れる確率がPageRank
34
３．PageRankの仕組み ～モデリング～
突然無関係なページへ遷移
35
３．PageRankの仕組み ～簡単な例～ PageRankの計算方法 ID=1 閉じたWWWを考える 3ページで構成 ID=2 ID=3
36
３．PageRankの仕組み ～簡単な例～ PageRankの計算方法 ½, 0, ½ A = ID=1 1/2 1/2 1 0, ½, ½
0, ½, ½ ½, 0, ½ 1, 0, 0 隣接行列 A = ID=3 ID=2
37
３．PageRankの仕組み ～計算手法～ 一般化 現在の存在確率に をかけると １ステップ先の存在確率が求まる
38
３．PageRankの仕組み ～計算手法～ 一般化 の定常状態の値がPageRank
39
３．PageRankの仕組み ～計算手法～ PageRankの計算方法 固有値、固有ベクトル
40
３．PageRankの仕組み ～計算手法～ PageRankの計算方法
41
３．PageRankの仕組み ～計算手法～ 続き(1)
42
最大固有値の固有ベクトルを正規化したものに一致
３．PageRankの仕組み ～計算手法～ 続き(2) PageRankは 最大固有値の固有ベクトルを正規化したものに一致
43
PageRankを求めるための計算量を大幅に軽減できる
何が言えるか？ PageRankを求めるための計算量を大幅に軽減できる
44
３．PageRankの仕組み 現実問題 全てのWebサイトがリンクでつながっているわけではない Dangling Linkの存在
45
３．PageRankの仕組み 解決法 ネットサーファーは時折全く関係のない ページへ飛ぶ
46
３．PageRankの仕組み マルコフ連鎖におけるエルゴード性
遷移によって任意の状態から全ての状態へ 移ることができればエルゴード的であることが言える つまり、ネットサーファーの気まぐれがエルゴード性をもたらす 先ほど計算した手法を現実に適用できる
47
３．PageRank Googleの例(1) ネットサーファーが「無関係なページへ飛ぶ確率」は0.15/1.15(13%程度)
48
３．PageRank Googleの例(2) 逆に、全く関係のないページから遷移してくる確率も0.15/1.15(13%程度)
49
３．PageRankの仕組み PageRankの計算方法 PR:ページランク C:ページから出て行くリンク数
d:リンクを辿って次の状態へ遷移する確率 rp
50
３．PageRankの仕組み ～まとめ～ 定量的に解析可能 現実的な計算量でPageRankを算出 PageRankが一意に定まる
Googleでは7500万ページを5時間
51
３．今後の展望 Indexerの並列分散化 検索アルゴリズム Linuxクラスタによって低コストで高速化 汎用的なフレームワークとして実装
PageRankを含めた優れた検索アルゴリズムの模索
52
３．今後の展望 Indexerの並列分散化と汎用化 Rule Index Indexer Anchor Index Repository
Similar presentations
