グラムベース全文検索システムの高速化と応用

スポンサーリンク

概要

論文の詳細を見る
本稿では, ニ次記憶に格納された大容量テキスト中から任意の文字列を高速に検索するため, グラム(一定長の連続する文字列)に基づいたインデックスと検索アルゴリズムを説明し, その応用について述べる. 基本的アイデアは, 一定長(L)の全グラムについて, その文字列が出現するテキスト中の位置を検索部としてコンパクトなデータ構造に記憶する点である. この長さL用の検索部を用いて, キー長Lの文字列のみならず, L未満およびLを超える文字列についても, 効率的に文字列検索できる. テキスト中の最初のパターンを見つけるために要する二次記憶へのアクセス回数は, キー長l_kがL以下のとき2回, そうでない場合は2(l_k-L+1)回である. また, 全マッチパターンを見つけるまでの時間は, マッチ数のみに比例する最小限の増加率になっている.
一般社団法人情報処理学会の論文
1998-01-19

著者

関連論文

もっと見る

スポンサーリンク