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

字符串集高速模式提取算法的开发与实现

• 批准号: 14780226
• 负责人: 篠原 歩
• 金额: $ 2.05万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780226/
• 关键词: パターン発見; データマイニング; 文字列処理; 探索; アルゴリズム; データ構造

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

直到去年，我们已经开发了一种算法，以查找一个图案，该模式是从今年的弦乐集中进行的，这是我们的旨在促进更多灵活性的。通过将模式组合起来，如果执行此扩展，探索空间将进一步扩展，因此我们将增加计算时间辞职并不是很好的线性，因此很难使用较大的尺寸字符串，该效果通过计算器实验证明，另外，为图案发现问题提供了有效的算法，该算法通过自由提供两种模式的相对距离来提高表现力。匹配高速给定的字符串，它是一个不均匀的尾随字符串，使用3分钟的树和压缩。 。

项目成果

Masahiro Hirao et al.: "A practical algorithm to find the best subsequences patterns"Theoretical Computer Science. Vol.292. 465-479 (2003)

Masahiro Hirao 等人：“寻找最佳子序列模式的实用算法”理论计算机科学。

S.Inenaga et al.: "The Minimum DAWG for All Suffixes of a String and Its Applications"Lecture Notes in Computer Science. 2373. 151-165 (2002)

S.Inenaga 等人：“字符串所有后缀的最小 DAWG 及其应用”计算机科学讲义。

M.Hirao et al.: "A practical algorithm to find the best subsequences patterns"Theoretical Computer Science. 292(2). 465-479 (2003)

M.Hirao 等人：“寻找最佳子序列模式的实用算法”理论计算机科学。

S.Inenaga et al.: "Space-Economical Construction of Index Structures for All-Suffixes of a String"Lecture Notes in Computer Science. 2534. 86-97 (2002)

S.Inenaga 等人：“字符串所有后缀索引结构的空间经济构造”计算机科学讲义。

H.Bannai et al.: "A String Pattern Regression Algorithm and Its Application to Pattern Discovery in Long Introns"Genome Informatics. 13. 3-11 (2002)

H.Bannai 等人：“字符串模式回归算法及其在长内含子模式发现中的应用”基因组信息学。