文字列集合からの高速パターン抽出アルゴリズムの開発と実働化

昨年度まで,入力として与えられた文字列集合から,それを特徴付ける一つのパターンを高速に見つけるアルゴリズムの開発をさまざまなパターン族に対して行ってきた.最終年度にあたる本年度は,それをさらに推し進め,複数のパターンの組み合わせによってより柔軟な表現を可能にすることを目指した.当然のことながらこの拡張を行うと,探索空間がさらに広がるために計算時間の増大が問題となる.我々は,接尾辞木を巧妙に活用することによって,与えられた文字列集合を特徴づけるのに最もよいパターン対を効率よく見つけるアルゴリズムの開発に成功した.接尾辞木は,線形サイズとはいえ領域効率があまりよくないため,大規模な文字列に対しては適用しにくくなる.そこで我々は,より領域効率のよい接尾辞配列を用いて接尾辞木を模倣することによって,実装上の観点からも有効なアルゴリズムを与え,計算機実験によってその効果を実証した.また,2つのパターン対の出現する位置の相対距離に関する条件を自由に与えることによって,より表現力を高めたパターン発見問題についても,効率のよいアルゴリズムを与えることができた.さらに,候補となるパターンが与えられた文字列に合致するかどうかを高速に判定するためのデータ構造として,3分木を活用した有向無閉路文字列グラフや,圧縮無閉路文字列グラフについての考察を行った.そしてこの一連のパターン発見問題に関する我々の研究を関連研究と比較しながら総括した.

昨年度まで,入力として与えられた文字列集合から,それを特徴付ける一つのパターンを高速に見つけるアルゴリズムの開発をさまざまなパターン族に対して行ってきた.最終年度にあたる本年度は,それをさらに推し進め,複数のパターンの組み合わせによってより柔軟な表現を可能にすることを目指した.当然のことながらこの拡張を行うと,探索空間がさらに広がるために計算時間の増大が問題となる.我々は,接尾辞木を巧妙に活用することによって,与えられた文字列集合を特徴づけるのに最もよいパターン対を効率よく見つけるアルゴリズムの開発に成功した.接尾辞木は,線形サイズとはいえ領域効率があまりよくないため,大規模な文字列に対しては適用しにくくなる.そこで我々は,より領域効率のよい接尾辞配列を用いて接尾辞木を模倣することによって,実装上の観点からも有効なアルゴリズムを与え,計算機実験によってその効果を実証した.また,2つのパターン対の出現する位置の相対距離に関する条件を自由に与えることによって,より表現力を高めたパターン発見問題についても,効率のよいアルゴリズムを与えることができた.さらに,候補となるパターンが与えられた文字列に合致するかどうかを高速に判定するためのデータ構造として,3分木を活用した有向無閉路文字列グラフや,圧縮無閉路文字列グラフについての考察を行った.そしてこの一連のパターン発見問題に関する我々の研究を関連研究と比較しながら総括した.