転置インデックスとは？
状態:-
閲覧数:2,413
投稿日:2017-03-06
更新日:2017-03-19
索引を格納するデータベースやファイル
・全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造
・転置索引、転置ファイル、逆引き索引などとも呼ばれる
・全文検索を行う対象の文書群から、単語の位置情報を格納するための索引構造のことである。情報処理テクノロジにおける転置インデックスは、単語や数字などに含まれているデータベースやドキュメント群へのマッピングを保持するインデックス型のデータ構造で、ドキュメント群へのマッピングの場合、検索エンジンが実現されている。
また検索キーが単語であり、連想配置の値が位置情報である場合は、ハッシュテーブルの形態を取る場合もある。転置インデックスには、大きく2つの手法がある。1つは、レコード単位転置インデックスと呼ばれるもので、単語とその単語を含む全文書をリストとして備えている。
もう1つは、単語単位インデックスである。単語を含んだ全文書以外にも、その単語が文書中のどこに現れるかという位置情報も含んでいる。また、単語単位転置インデックスの実装にも、いつくかの手法がある。
その中でももっとも単純なものは、全文書のIDとその保存位置情報をペアとして格納したものである。
平仮名
・てんちいんでっくす
英語
・Inverted index
「転置インデックス作成」の略称
・転置インデックスを作成する処理
・全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造
・転置索引、転置ファイル、逆引き索引などとも呼ばれる
・全文検索を行う対象の文書群から、単語の位置情報を格納するための索引構造のことである。情報処理テクノロジにおける転置インデックスは、単語や数字などに含まれているデータベースやドキュメント群へのマッピングを保持するインデックス型のデータ構造で、ドキュメント群へのマッピングの場合、検索エンジンが実現されている。
また検索キーが単語であり、連想配置の値が位置情報である場合は、ハッシュテーブルの形態を取る場合もある。転置インデックスには、大きく2つの手法がある。1つは、レコード単位転置インデックスと呼ばれるもので、単語とその単語を含む全文書をリストとして備えている。
もう1つは、単語単位インデックスである。単語を含んだ全文書以外にも、その単語が文書中のどこに現れるかという位置情報も含んでいる。また、単語単位転置インデックスの実装にも、いつくかの手法がある。
その中でももっとも単純なものは、全文書のIDとその保存位置情報をペアとして格納したものである。
平仮名
・てんちいんでっくす
英語
・Inverted index
インデックス作成とは？
「転置インデックス作成」の略称
・転置インデックスを作成する処理
全文検索システム
全文検索システム
Google その他の全文検索システムでは転置インデックスというデータ構造を予め作成し、高速に検索できるようにしている
・MySQL や PostgreSQL 等の RDBMS にも全文検索のための転置インデックス作成機能があるが、日本語に対応していないという問題がある
・MySQL でも Senna を使えば日本語の全文検索ができる
Senna
転置インデックスを用いた日本語対応の高速な全文検索を可能にするライブラリ
・N-gram 系
・Senna には MySQL と連携するためのパッチが標準でついている
・PostgreSQL についても NTT データが提供している Ludia を追加することで Senna と連携可能になる
転置インデックスの仕組み
各単語と単語を含む文書IDからなるテーブル
（注：実際には単語が文書の中で出現した位置情報を含む場合が多いが、本稿では割愛）
例
・2つの英語の文書（Doc 1,Doc2）がある
・そのコンテンツがそれぞれ「I love Emacs」「I prefer Vim to Emacs」
・このとき、以下の表のような転置インデックスを生成
・説明に利用する転置インデックスは「連想配列」というデータ構造で実装でき（注：連想配列でない実装もある）、単語をキーにして文書ID のリストを返す
表
・転置インデックスの例
| 単語 | 文書IDリスト |
|---|---|
| I | 1,2 |
| love | 1 |
| Emacs | 1,2 |
| prefer | 2 |
| Vim | 2 |
| to | 2 |
・クエリに対する結果を返す処理は簡単
・例えば、ユーザーが「Vim」というクエリを発行すると、検索エンジンは「Vim」を含む文書IDリストを返す
・表では文書IDの「2」を返す
検索エンジンの常識をApache Solrで身につける
転置インデックス
第3回 転置索引とは何か？：検索エンジンはいかにして動くのか？
転置インデックスの基礎
転置インデックスとは
転置インデックスの構造から見る全文検索
転置インデックスで日本語を検索する際の仕組み
転置インデックスを利用した検索とgrepによる検索を比較してみる
転置インデックスを実装しよう
転置インデックスとTop
悟空、秘剣「転置インデックス」を手に入れる
Mroongaの完全転置インデックスによる全文検索はどのくらい速いのか
検索エンジンを実装 (1)転置インデックス作成
転置インデックスに位置情報を付与する新手法
「転置インデックス」
文単位転置インデックスによる近接検索手法
全文検索システム「SOLR」の紹介 - 第2回「全文検索の仕組み」