Edited at

転置インデックスの基礎

More than 3 years have passed since last update.


転置インデックスの概要

文章検索の速度を高めるために、転置インデックスを用いることが効果的

である理由とその仕組み。


構造

転置インデックスは各文書の内容を単語ごとに分割し、キーとする。

値にその単語が登場する文章を入れる。

これによって単語で検索する際にそれが含まれる文書が値として出力される。

転置インデックスは単語の数(キーの数)が多くなるにつれて検索の時間が

長くなるため、キーをハッシュ化し、分割することで検索の時間を削減

することができる。

また、日本語の取り扱いは注意が必要。

日本語は英語と異なり、単語同士が結合しているため検索内容と

転置インデックスのキーの内容と異なる場合が想定される。

例)

入力:「全文検索」

転置インデックスキー:「全文」,「検索」

この場合、転置インデックスに入力内容である「全文検索」が含まれて

いないため、出力はゼロとなる。

これを防ぐために、入力内容を形態素解析することで、検索内容と

転置インデックスのキーの内容を揃えることで解消できる。

更に検索の精度を高めるために、転置インデックスの各単語が文書に出現

した場所を記録させることで複合ワードの検索の精度が高まる。

これを完全転置インデックスという。


まとめ

転置インデックスの流れは以下である。


  1. 文章を形態素解析し、単語ごとに分ける

  2. 単語をキーとして、その単語が出現した文書を値とする
     更にその単語が出現した場所もインデックスする。

検索の流れは以下である。

1.入力クエリを形態素解析する

2.形態素解析されてそれぞれのキーワードを転置インデックスで検索

 させて、それぞれのキーワードが隣合うものを出力させる