検索システムおよび インデクシング 毎日使っている検索エンジンの仕掛 けについて大雑把なところを学ぶ 世界中のインターネットＨＰ生産者を 渡り歩いて、商品（＝ＨＰ）買い付け インターネット crawler indexing Crawled pages Inverted index file search engine 検索エンジンの概略 集めた商品（＝ＨＰ Crawled papges）の仕分けをして、お客さん の要望に即時に応えられるように商品目録（＝inverted index file）を作成する。 インターネット crawler indexing Crawled pages Inverted index file search engine 検索エンジンの概略 お客さんの要求（query 検索質問）に応えて、inverted index file を探し、商品、ではなくて商品のありかを教える インターネット crawler indexing Crawled pages Inverted index file search engine お客は、教えてもらった商品のありかを自分で辿って（もっとも クリックするだけですが）、欲しい商品を取ってくる。 ただし、ときどき商品が教えてもらった場所にないこともある。 インターネット Not found = dead link（リンク切れ） crawler indexing Crawled pages Inverted index file search engine 検索エンジンの概略 インターネット crawler indexing Crawled pages Inverted index file search engine 利用者の質問に対する検索時の動き Posting file 質問：Q 再質問 検索エンジン： Qに一致する 文献への ポインタを探す DOC1 DOC2 DOC3 : Ｗｅｂ pages doc1 doc2 doc3 Webページ本体 あるいは snippet sippetが表示できるというこ とは、実は検索エンジンは 商品（＝ＨＰ）を自分のとこ ろでも持っているのですね。 なんだか変？ 転置インデックス インデックス ターム ヒット 件数 科学 ２ 研究費 １ 申請 ３ ポスティングファイル ポインタ URL Doc1 Doc3 Doc1 Doc4 Doc5 Doc2 ポインタ Web Webページ本体 Doc1 Doc2 Doc3 Doc4 Doc5 Doc6 Doc7 検索システムの構造 1. 2. 3. 4. 5. 検索対象のWebページ各々は、それに現れる複数の語( 以下「ターム (term) 」と呼ぶ) によって特徴付けられる。タームによるWebページの特徴付 けをインデクシング(indexing) という。 利用者は自分が欲しい文献を特定する記述を質問Q として検索システムに 与える。質問は、1 個以上のキーワード、あるいは自然言語文で記述される 検索エンジンは、Q を解釈して、それに適合するWebページを検索する。適 合するWebページは一般的には複数存在する。したがって、検索結果は、ポ スティングファイルへのポインタの集合である。ポスティングファイルは、 ( Webページ識別子、Webページの格納されているアドレス) というペアから なる。 Webページ本体は検索システム内で集中管理されている場合と、インター ネット上に散在する場合がある。後者の場合、ポッスティングファイルのWeb ページ格納アドレスは、URL あるいはURI である。 利用者には検索結果として検索されたWebページのURL などのアドレスが 返される。多くの場合、 WebページにはWebページのURL へアクセスできる リンクが張ってあり、クリックすればURL にアクセスして文献が表示できる。 ターム と 検索 統制ターム: 予め決められたタームだけを使う。 タームの質は統制により維持されるが、利用者 が統制タームしか質問に使えない。 古い時代には大規模なタームを抽出する自動 的技術もなく、人手でターム抽出をしていた。 自由ターム: 任意のタームを質問に使える。後 に述べる全文検索ではWebページ中のタームを 網羅するので、自由タームになる 90年代以降、ターム抽出の自動化、インデク スも自動的に構築できるようになった。 完全一致検索（ブーリアン検索） ブール式で書かれた質問の条件に一致する ページ全てを見せる。検索は高価だった時代 の遺物という見方もあるが、検索の基礎的考 え方なので知っているべき。昔は検索する といくら、というお金を取られた時代だった。 最良優先検索（ベクトル空間法など） 良いもの（=質問への適合度の高いページ）か ら順に見せていこうという考え方。 転置インデックスの高速検索 膨大な数のキーワードの中から質問として 与えられたキーワードを高速に検索するこ とが重要 Ｂ木 トライ PATRICIA木 B木 膨大な数のキーワードの中から質問として与えられたキーワードを高速に 検索することが重要 ( *F * M * ) ( * Al * Br * E * ) [Afgan | 2 | * | ] posting file ( * Gr * H * Ja * L * ) ( * Rut * Uni *) Trie（トライ） トライは2 分木で、左ポインタは登録単語の内部の次の文字、右ポインタは左部分木 に入らなかった登録単語のうちアルファベット順の次の登録単語の先頭文字 あ さ い ＊ひ ＊ぬ や ＊け ご ＊や く ＊し く る ぼ ＊ま ＊う よ ＊け PATRICIA木 PAT 木とは、トライにおいて、非分岐ノードを省略し、その代わりにノードに 木の深さ情報を追加したもの あ（１） ＊ひ（３） ＊け（５） い（２） ＊ぬ（３） ＊ご（４） ＊や（６） ＊し（４） ＊ま（６） ＊う（７） ＊け（８） あさひ、あさやけ、いぬ、いぬごや、いぬくぼう、くし、くるま、くるまよけ 全文検索 メモリ中にあたかも全文が格納されているかのような状態で検索 本当に全文が格納されている場合＝長大な文字列マッチ処理 本当はなんでもかんでもインデックスされた場合＝インデックスの効率化 全文検索でできそうな検索質問 「ターム「情報」の前後n 文字以内の範囲にターム「収集」が現れる」 「ターム「分析」と「統合」が同じ段落に現れる」 インデックスの作り方 文字列を十分に長くとれば全ての半無限長文字列は異なるものになる。そ の上で文字列を辞書式にソートすると言語の統計で説明したKWIC になる。 そして、葉が反無限長文字列の開始位置をデータに持つTrie やPATRICIA 木を作れば、KWIC は全文検索向きのインデクスとして使える。 半無限長文字列の代わりに1 単語を葉とするTrie やPATRICIA 木にすると コンパクトになるが、葉にはWebページにおいて複数回現れるその単語開始 位置を全て記述しておく。これもインデクスとして使える。 Suffix Array 最近の機械翻訳では、対訳辞書をコーパスから学習する研究が多い 1 4 11 13 16 22 26 この例文の Suffix Array は辞書式にならべた各単語の開始位置を記載し た配列 ２２ ４ ２６ １６ １ １３ １１ ２分探索で高速サーチ Supra Index 学習 ２２ 対訳 コーパ ス ４ ２６ １６ １ １３ １１ 質問の拡張 • 質問語の追加 • 関連性フィードバック 目的 全く別の意図 検索結果を見て満足 し、初期の意図は達成。次に全く異な る意図の質問に切り替わる場合 意図の更新 検索結果に一応の満足 は得たが、結果を見て少し異なる視点から さらに検索を続けたくなった場合 元の意図に沿うように 検索結 果に満足できなかったので、元々の意図を 達成するために質問を変える場合 質問語の追加 • • • • • • • 質問者が与えた質問のインデックス語をシステム側で増強してしまう 方法 「Windows 」という質問を考えてみよう。シソーラスは次のもの IT 技術 パソコン ワークステーション PC/AT OS Linux Windows Windows98 WindowsNT • 一般的な質問にしたければ上位の「OS]や「パソコン」を加え、より特 殊な質問にしたければ下位の 「Windows98 」 「WindowsNT」 を加える 関連性フィードバック、あるいは適合性フィードバック • Relevance Feedback • 第i 回めの質問 qi の結果、N+個の質問に適合したWebページと、 N-個の不適合なWebページが得られたとする。適合性の判定はひと まず質問者が行なうとしておく。このとき、第i +1 回めの質問 qi+1 を次式によって作る q i1 q i • • • • N N D j D j j1 j1 Dj+適合Webページj のインデックス, Dj- 不適合Webページj のイン デックス α＝１、β＝１ をIdeの式という 1 1 N N α＝ 、β＝ をRoccioの式という N q i1 q i D j D1j j1 をIde dec-hi の式という Pesudo Relevance Feedback • 大量に検索結果があれば、適合Webペー ジを判定することも難しい。そこで、人手に よる適合性の判定をやめて、最上位にラン クされたWebページを正解として、そのWeb ページだけのフィードバックをかける
© Copyright 2024 ExpyDoc
