Factor-Oracleを用いた反復部分文字列の効率的な抽出

概要

論文の詳細を見る
Factor oracleはsuffix automatonに類似したオートマトンで与えられた文字列から線型時間・空間で生成され,その文字列の全ての部分文字列を受理するという性質がある.suffix automatonなどの類似した構造に比べて生成アルゴリズムが単純であるなどの利点の一方,欠点もある.例えば,suffix automatonやsuffix treeは全文検索の索引に用いたり,繰り返し出現する部分文字列を抽出するなどに応用できるが,factor oracleこれを完全に行なおうとすると非効率的であった.しかし,[加03a]で示されたfactor oracleに関する新い性質を用いると,これらの処理をもっと効率的に行える可能性がある.本論文では,factor oracleを用いた反復部分文字列の近似的抽出アルゴリズム([LL00])を元にして,[加03a]の性質を用いて完全な最長反復部分列を求める遅いアルゴリズムと,[LL00]の近似精度を僅かなオーバヘッドで大きく向上させるアルゴリズムの二つを提案する.後者は別の改良[LLA02]よりも実行効率の面で特に優れている.
一般社団法人情報処理学会の論文
2004-01-30