テキストインデックスのテクニックとは？転置インデックスとシグネチャファイルの仕組みを解説

テキスト検索（情報検索）の分野では、大量の文書の中から目的の情報を高速に取り出すために、さまざまな索引（インデックス）手法が活用されています。中でも代表的なのが転置インデックス（Inverted Index）とシグネチャファイル（Signature File）の2つです。本記事では、それぞれの仕組みと検索方法、長所・短所をわかりやすく解説します。

転置インデックス（Inverted Index）とは

転置インデックスは、「document_table（文書テーブル）」と「term_table（用語テーブル）」という2つのテーブルを、ハッシュインデックスまたはB+木インデックスによって管理する索引構造です。

document_table（文書テーブル）

文書レコードの集合で構成され、各レコードは次の2つのフィールドを持ちます。

• doc_id：文書を一意に識別するID
• posting_list：その文書に出現する語（または語へのポインタ）のリスト。何らかの関連度の尺度に従って並べられます。

term_table（用語テーブル）

用語レコードの集合で構成され、各レコードは次の2つのフィールドを持ちます。

• term_id：用語を一意に識別するID
• posting_list：その用語が出現する文書（レコード）の識別子のリスト

転置インデックスによる検索の手順

転置インデックスを使えば、与えられた用語の集合に関連するすべての文書を特定できます。例えば、ある用語群に関連する文書を探す場合、まず用語テーブルから各用語に対応する文書識別子のリストを取得し、それらの共通部分（交差）を求めることで、関連するレコードの集合を得られます。逆に、与えられた文書の集合に関連するすべての用語を見つけることも可能です。

長所と短所

転置インデックスは市場で最も広く採用されている手法であり、実装も比較的簡単です。その一方で、ポスティングリストが非常に長くなるケースがあり、ストレージの必要量が大きくなるという課題があります。また、同義語（綴りは異なるが意味が同じ語）や多義語（1つの語が複数の意味を持つ語）への対応は十分とは言えません。

シグネチャファイル（Signature File）とは

シグネチャファイルは、データベース内の各レコードに対してシグネチャ（署名）データを保存しておくファイルです。各シグネチャは、語を定義するための固定長（bビット）のビット列として表現されます。

シグネチャの生成方法

単純なエンコーディング方式では、まずレコードのシグネチャの全ビットを0に初期化します。その後、あるビットに対応する語がレコード内に出現していれば、そのビットを1にセットします。

シグネチャのマッチング判定

シグネチャS₁が別のシグネチャS₂とマッチすると判断されるのは、S₂で1になっているすべてのビットが、S₁でも1になっている場合です。ただし、一般に語の総数は利用可能なビット数よりも多いため、複数の語が同じビットに割り当てられる（多対一のマッピング）ことがあります。

課題と改善策

この多対一のマッピングが原因となり、クエリのシグネチャに一致したレコードが、必ずしもクエリのキーワード集合を含んでいるとは限らず、検索コストが高くなります。そのため、候補となったレコードについては、実際に取得・解析・ステミング（語幹抽出）を行い、照合を確認する必要があります。

改善策としては、まず頻度分析・ステミング・ストップワードの除去を実行したうえで、ハッシュ法や重畳符号化（superimposed coding）の技術を用いて、語のリストをビット表現へエンコードする方法が有効とされています。