Factor-Oracleを索引に用いた全文検索アルゴリズム

概要

論文の詳細を見る
Facotr Oracle [1]を索引に用いた,パターンの長さに対してほぼ線形時間の全文検索アルゴリズム提案する.Factor Oracleは任意の有限アルファベット文字列から生成される効率的なオートマトンで少なくとも,元の文字列の部分列(Factor)を全て受理する.文字列pから生成されたFactor Oracle, Oracle (p)がパターンwを受理しなかった場合はwは確実にp中に部分列として存在しない.しかしながらOracle (p)の部分列ではない文字列を受理する可能性がある.そのためFactor Oracleをそのまま索引構造に使うことはできなかった.本論文ではFactor Oracleに若干の修正を加えることによって,ある文字列wがOracle (p)に受理されたとき,wがpの部分列であるか否かを|w|にほぼ比例した時間で判別するアルゴリズムを提案する.また,このアルゴリズムではwのp中でのすべての出現箇所を効果的に特定することも可能である.
社団法人電子情報通信学会の論文
2003-10-20