1号
2号
検索対象の文書を集めるロボ
索引を構築するロボ
準備 :
検索エンジンの索引構造
31
1号
2号
3号
検索対象の文書を集めるロボ
索引を構築するロボ
索引の検索を行うロボ これの事前知識
検索エンジンの索引構造
• 転置インデクス (inverted index) と呼ばれる データ構造を用いる
– 本の索引と基本的に同じ
見出し語
北大 (DocID; <position>, DocID; , … 辞書 (dictionary) /
語彙 (vocabulary) 転置リスト (inverted list)
具体例
見出し語 北大 講義 検索 エンジン
1; <3, 8>, 2; <1>, … 1; <5>, …
1; <10>, …
1; <11>, …
見出し語の決め方
• 検索の観点から適切な単位で区切る必要あり
– 実はとても大切な問題
– 日本語の場合は「形態素解析」と呼ばれる言語処 理技術が利用されている
• 本講義では「適切な単位」で見出し語を切り出
すモジュールがあるという前提で話を進める
辞書に必要な情報
•
見出し語と，見出し語に対応する転置リストへのポインタを保持– ポインタ =メモリ／ディスク上の番地番号
•
辞書の実装に用いられるデータ構造– ハッシュテーブル – トライ木
• パトリシアトライ，ダブル配列など
– 簡潔データ構造
• LOUDSなど
見出し語 転置リスト
北大 0x112233
講義 0x112245
検索 0x112252
エンジン 0x112260 35
t r e e i e
DocID; <position>, DocID; , … DocID; <position>,…
DocID;
h o k
◆トライ木の例
◆辞書の要件
転置リストの実装例
• 使い方に応じて格納形式を選択
– DocID のみ
– DocID + Position
見出し語 北大 講義
Freq: DocID, DocID, …
補足 : Google ではどうやっているか ?
•
位置情報のみの転置リストを利用[Dean+ 09]
•
この場合「位置情報⇒
文書ID
」の変換が必要–
例えば下図のような変換テーブルを二分探索37
文書ID 開始位置
1 1
2 120
3 180
… …
N 17280
見出し語 北大 講義 検索 エンジン
Freq: position, position, …
[Dean+ 09] Jeffrey Dean, “Challenges in Building Large-Scale Information Retrieval Systems”, WSDM ‘09 Tutorial, 2009.
補足 : 二分探索のチカラ
• 1 億文書の探索コスト
– log2 (10^8) ≒ 25 回
10152025
log2(x)
脱線 : 人力二分探索
• 未知の言語の辞典
–
謎の単語“Jingisukan”
を調べる–
辞典の中身はどうやらアルファベット順–
けれど単語に用いられるアルファベットの分布は未知どうやって探す ?
本を開くのはとても疲れるので 本を開く回数は最小にしたい
辞典
脱線 : 最後の方
わざわざ二分探索するのもどかしい !
• CPU
も似たような特性を持つ–
メモリのある部分を読み込んだ際に先読みしてキャッシュに格納–
さきほど読み込んだ部分の後ろを探していく場合には，キャッシュ内を参照するため，メモリからデータを取得する必要がない
–
二分探索の初期はキャッシュミスを引き起こす
キャッシュ
CPU まずここを探す
索引の構築
1号
2号
3号
検索対象の文書を集めるロボ
索引を構築するロボ
索引の検索を行うロボ 41
索引の構築
• 入力文書を転置インデクスに変換する
2号
文書群 転置インデクス