シグネチャ法

シグネチャ法（ - ほう）とは全文検索システムにおけるインデックス作成手法のひとつ。全文検索用インデックスとしてもっとも利用されている転置ファイル方式と比べると、検索速度、機能性こそ引けを取るが、「原理が単純で実装が容易」「grepのような逐次検索よりは高速」といった利点がある。シグネチャ (signature) とは英語で「署名」の意味である。

インデックス作成原理

1. 文書を単語単位に分割する。
2. 単語からハッシュ値を得、それに対応するビットを反転させた固定長のビット列を作成する。
3. 文書に含まれる全ての単語からビット列を得、その論理和を文書の「シグネチャ」とする。
4. 全ての文書のシグネチャを1つのファイルにまとめて出力する（シグネチャ・ファイル）。

特徴的なのは、ある単語の出現を特定のビットが0であるか1であるかによって表すところである。これにより高速なインデックスの作成が可能となる一方、すべての単語の出現有無を512～1024bit 程度のビット列に配置しなければならないため、複数の単語が同一ハッシュを持つという「ハッシュの衝突」が避けられない。これにより、異なる単語が同一のビット位置を持つこととなるため、多数の誤検出が発生してしまう。そのため、シグネチャ法ではシグネチャによって検索候補として選び出されたファイル群をgrep検索することにより、最終的に目的の単語を含む文書を選び出す手法をとっている。

その構造からわかるとおり、シグネチャ法はあまり大規模な検索システムに利用されることはない。

外部リンク

• G-BASEにおけるシグネチャファイルの実装と性能評価
• インターフェイスの街角(23)シグネチャ法によるお手軽検索システム