木構造を用いた高速な全文検索について

概要

論文の詳細を見る
本稿では、テキスト中から任意の文字列を特に高速に検索するため新しいデータ構造と、それを用いた検索アルゴリズムを提案する。基本的アイデアは、一定長(L:レベル)の文字列全てについて、その文字列が出現するテキスト中の位置を検索部としてコンパクトなデータ構造に記憶する点である。この長さL用の検索部を用いることにより、キー長Lの文字列のみならず、L未満およびLを超える文字列の検索も効率的に行うことができる。本稿での提案に関連し、日本語を対象とした全文検索システムで1文字単位ないし2文字単位の転置ファイルを利用したシステムの稼働例が上げられているが、日本語の場合、文字数が多いため検索部が大きくなる問題が指摘されており、文字種に応じた複数の検索構造を作成する工夫がなされている。本稿でのレベルLが1ないし2以上の場合に関連しているが、従来の研究では、キー長がL未満の文字列の検索は扱ってない。また、複数文字単位の転置ファイルに基づいている点は共通だが、本稿で提案インデックス部は二次記憶へのアクセス回数を極力減少するデータ構造に構成されている点でも特徴を有する。提案の手法は、検索部として用いるデータ構造のみで、当該文字列を含むテキスト中の位置を知ることができるため、署名ファイル、PAT木など存在の可能性のみを知る手法に比べ、精度の高い方法と言える。また、提案の方法は、転置ファイルなど単語ごとのインデックスによるものではなく、すべての文字列を検索の対象とするものである。即ち、作成される検索高速化のためのデータ構造は、単語をはじめテキストの文法上のいかなる性質にも依存していないため、広範囲な言語、ビット列や遺伝子情報などのあらゆるストリングマッチに適用可能である。
一般社団法人情報処理学会の論文
1996-09-04

木構造を用いた高速な全文検索について

スポンサーリンク

概要

著者

関連論文

スポンサーリンク