検索エンジンに関して The Anatomy of a Large-Scale Hypertextual Web Search Engine 2003/05/27 M1 藤本　浩史

発表の流れ 研究の概要 検索エンジンの仕組み PageRank 今後の展望

１．研究の概要 検索エンジン 分散Indexer（インデクサ）の実装

２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher

２．検索エンジンの仕組み ～Crawler～ WWW上を自動的に巡回してWebページを収集する検索ロボットプログラム

２．検索エンジンの仕組み ～Crawler～ 「Crawler」がWWWからドキュメントを 収集し「Store Server」に渡す 「Store Server」はページごとに一意の｛docID｝を割り当て、圧縮してRepositoryに保存

２．検索エンジンの仕組み ～Crawler～ Store Server Crawler docID WEB Crawler Crawler Compress Crawler Repository

２．検索エンジンの仕組み ～Crawler～ Repository Data Structure docID ecode urllen pagelen url page docID: Webページ（URL）に対する一意のID page : 実際のWebページコンテンツ

２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher

２．検索エンジンの仕組み ～Indexer～ Crawlerが収集したWebページを解析し検索に使用するためのインデックスを生成

２．検索エンジンの仕組み ～Indexer～ 形態素解析 Forward Index（正引き索引）作成 Inverted Index（逆引き索引）作成 アンカー（リンク）切り出し

２．検索エンジンの仕組み ～Indexer～ 形態素解析 自然文から品詞ごとの単語を切り出す > 日本語では辞書を使用

２．検索エンジンの仕組み ～Indexer～ Forward Index ページに含まれる単語を{wordID}に置き換える {docID}に{wordID}リストを割り当てる Google Web Images Groups Directory {Null} ・・・・・・ {docID} {wordID} {params}

２．検索エンジンの仕組み ～Indexer～ Inverted Index Forward Indexを元に{wordID}⇒{docID}のインデックスを作成する 検索で使用されるのはこのインデックス Google Web ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek

２．検索エンジンの仕組み ～Indexer～ アンカー切り出し Webページからリンクを切り出す URLを相対リンクから絶対リンクへ

２．検索エンジンの仕組み ～Indexer～ プログラム > Indexer：Forward Indexを作成 > Sorter ：Inverted Indexを作成 データベース > Lexicon：辞書（単語とwordIDをマップ） > Barrels：Indexを格納するデータベース

２．検索エンジンの仕組み ～Indexerの構成～ 形態素解析 decompress Repository Lexicon 辞書 docID 分散検索エンジン 分散 / 検索 / エンジン Webページに含まれる文書を、辞書を用いて単語に分解

２．検索エンジンの仕組み ～Indexerの構成～ Forward Indexの作成 docID wordID{エンジン} wordID{検索} wordID{分散} Indexer docID ｛分散｝ ｛検索｝ ｛エンジン｝ ｛Null｝ ・・・・・・ {docID} {wordID} {params} Lexicon この後にForward Indexのデータ構造を入れる Forward Index エンジン 検索 分散 Barrels

２．検索エンジンの仕組み ～Indexerの構成～ Inverted Indexの作成 Google hoge ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek Barrels Inverted Index Forward Index Sorter Lexicon 辞書

２．検索エンジンの仕組み ～Indexerの構成～ アンカーの切り出し docID Indexer <a>Link</a> decompress Anchor Repository このリンクを元にCrawlerが巡回

２．検索エンジンの仕組み Indexerの構成 decompress Repository Indexer Forward Index Barrels Lexicon Inverted Index Sorter

２．検索エンジンの仕組み 検索エンジンの構造 Crawler Indexer Searcher

２．検索エンジンの仕組み Searcher Webサーバー上で動作 ユーザーからの検索キーを受け付ける Indexerが生成したインデックスを参照して検索キーにマッチする検索結果を返却

２．検索エンジンの仕組み ～Searcher～ 検索キー Searcher Barrels Inverted Index

２．検索エンジンの仕組み ～Searcher～ 検索アルゴリズム テキストマッチ タグ重み付け キーワード頻出度 キーワードの出現位置 キーワード近接度 etc.

２．検索エンジンの仕組み ～Searcher～ テキストマッチ 検索キーと一致するテキストが文書内に含まれている Searcherの実際の挙動を説明 Google hoge ・・・・・・ {docID} {wordID} {params} Yahoo! InfoSeek 検索キー：hoge 【Inverted Index】

２．検索エンジンの仕組み ～Searcher～ タグ重み付け HTMLタグの種類により重みをつける ＜EX>Namazu タグの種類 タグの重み H1 8 A 4 STRONG 2 EM H2 7

発表の流れ 研究の概要 検索エンジンの仕組み Crawler Indexer Searcher PageRankの仕組み 今後の展望

３．PageRankの仕組み 質の高い検索結果を返すには？ サイトの質を内容から判別することは困難 定量的に解析できる手法を （Yahoo!のように人間が判断） 定量的に解析できる手法を ジャンクサイトを排除 従来の検索アルゴリズムを逆手に取る

３．PageRankの仕組み 基本概念 「多くの良質なページからリンクされているページは、やはり良質なページである」 Googleによって提唱

３．PageRankの仕組み ～概念～ PageRankの測り方 被リンク数 PageRankの高いページからのリンク （Yahoo!など） リンク元のリンク数

３．PageRankの仕組み ～概念～ PageRankの概念図 50 100 50 50 54 12 27 4 4 27 4 リンク

３．PageRankの仕組み ～モデリング～ Random Walker on the Web PageRankのモデリング ネットサーファーを考える Web上のリンクをランダムに進んでいく 決して前のページには戻らない 時折全く関係のないページへ飛ぶ ネットサーファーが、あるサイトを訪れる確率がPageRank

３．PageRankの仕組み ～モデリング～ 突然無関係なページへ遷移

３．PageRankの仕組み ～簡単な例～ PageRankの計算方法 ID=1 閉じたWWWを考える 3ページで構成 ID=2 ID=3

３．PageRankの仕組み ～簡単な例～ PageRankの計算方法 ½, 0, ½ A = ID=1 1/2 1/2 1 0, ½, ½ 0, ½, ½ ½, 0, ½ 1, 0, 0 隣接行列 A　= ID=3 ID=2

３．PageRankの仕組み ～計算手法～ 一般化 現在の存在確率に をかけると １ステップ先の存在確率が求まる

３．PageRankの仕組み ～計算手法～ 一般化 の定常状態の値がPageRank

３．PageRankの仕組み ～計算手法～ PageRankの計算方法 固有値、固有ベクトル

３．PageRankの仕組み ～計算手法～ PageRankの計算方法

３．PageRankの仕組み ～計算手法～ 続き(1)

最大固有値の固有ベクトルを正規化したものに一致 ３．PageRankの仕組み ～計算手法～ 続き(2) PageRankは 最大固有値の固有ベクトルを正規化したものに一致

PageRankを求めるための計算量を大幅に軽減できる 何が言えるか？ PageRankを求めるための計算量を大幅に軽減できる

３．PageRankの仕組み 現実問題 全てのWebサイトがリンクでつながっているわけではない Dangling Linkの存在

３．PageRankの仕組み 解決法 ネットサーファーは時折全く関係のない ページへ飛ぶ

３．PageRankの仕組み マルコフ連鎖におけるエルゴード性 遷移によって任意の状態から全ての状態へ 移ることができればエルゴード的であることが言える つまり、ネットサーファーの気まぐれがエルゴード性をもたらす 先ほど計算した手法を現実に適用できる

３．PageRank Googleの例(1) ネットサーファーが「無関係なページへ飛ぶ確率」は0.15/1.15(13%程度)

３．PageRank Googleの例(2) 逆に、全く関係のないページから遷移してくる確率も0.15/1.15(13%程度)

３．PageRankの仕組み PageRankの計算方法 PR:ページランク C:ページから出て行くリンク数 d:リンクを辿って次の状態へ遷移する確率 rp

３．PageRankの仕組み ～まとめ～ 定量的に解析可能 現実的な計算量でPageRankを算出 PageRankが一意に定まる Googleでは7500万ページを5時間

３．今後の展望 Indexerの並列分散化 検索アルゴリズム Linuxクラスタによって低コストで高速化 汎用的なフレームワークとして実装 PageRankを含めた優れた検索アルゴリズムの模索

３．今後の展望 Indexerの並列分散化と汎用化 Rule Index Indexer Anchor Index Repository