転置インデックスの有用性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/16 14:31 UTC 版)
「転置インデックス」の記事における「転置インデックスの有用性」の解説
検索エンジンを設計するとき、転置インデックスの必要性を考え、エンジンのアルゴリズム、その動作ステップを考慮することは重要なことである。たとえば、コーパスを使った手法で索引ファイルを作成することを考えてみる。アルゴリズムの手始めは、最初の文書をチェックして、単語ごとに分割することである。処理の最後に、文書中に現れる全ての単語の一覧とその出現位置をリストアップする。むろん、同じ単語は複数回にわたって出現する。したがって出現位置情報も1つだけとは限らなくなる。位置情報とは単語が文書中のどこに位置しているかであり、単語の出現に先立って現れた文字数をカウントすることだといえよう。たとえば、ある文書に最初に現れた単語は、文書中の最初の文字を含んでおり、すなわち位置情報は｢0｣であるといえる。2番目の単語は5文字目に出現するとする。したがって位置情報も｢5｣となる。 表形式にすると、次のようなものになるだろう。 単語ID単語位置情報1 dog 1,20,500,etc 2 cat 10,45,3445,etc 1つの文書だけでなく、コーパスを用いているので、各文書に現れる全ての単語を格納するのに、より大きなリストが必要となってくる。ここが検索エンジン設計者の見解が異なるところであり、すべての検索エンジンが同じ設計になっていない理由の1つである。 一般的な見解としては、各文書に連続してアクセスする際に、その都度、直接単語一覧を作成して格納していくことが手っ取り早い方法だろう。文書ごとに単語リストを格納していくと出来上がるのは我々がよく知るところの、いわゆる「索引」になる。この時点では文書あたりの単語リストであり、単語あたりの文書リストではないので転置索引（逆引き索引）ではなく正引き索引といえるだろう。以下がその例である。（検索エンジンによっては大きく構造が異なる場合もある） 文書ID含まれる単語IDと位置1 (1 at 1,20,500) (2 at 10,45,3445) 2 (1 at 3, 50, 60) (2 at 100, 120, 130,..) 3 etc 転置インデックスの基本的な概念はテーブルに対して「単語Xはどの文書にあるか」といったクエリの応答速度を最適化するということである。 上記のテーブルに対するクエリだと、一覧中の各項目を逐一チェックして、各項目について単語が存在するかどうかを確認しなければならないアルゴリズムとなる。転置インデックスとは文書ごとに単語を探すのではなく、単語ごとにそれを含む文書を一覧抽出するために、上記のテーブルの行列を｢転置｣させたものである。 同じ例で、転置インデックスは次のようになるだろう。 単語ID該当文書ID1 1,3,4,5 2 2,3,4 3 etc こうすることで、単語を含む文書を見付けるために、アルゴリズムは転置インデックスの単語IDにジャンプし、文書一覧を見付けてくることが出来る。これによって検索応答時間の大幅な短縮がなされることとなる。
※この「転置インデックスの有用性」の解説は、「転置インデックス」の解説の一部です。
「転置インデックスの有用性」を含む「転置インデックス」の記事については、「転置インデックス」の概要を参照ください。
- 転置インデックスの有用性のページへのリンク
