部分文字列増幅法による共通パターン発見アルゴリズム

情報処理学会 HANDLE Web Site 被引用文献2件 参考文献20件 オープンアクセス

書誌事項

タイトル別名
  • ブブン モジレツ ゾウフクホウ ニ ヨル キョウツウ パターン ハッケン アルゴリズム
  • A Pattern Discovery Algorithm by Substring Amplification

この論文をさがす

抄録

本論文では，複数の文字列に共通な部分を見つける問題を考察する．まず，この問題をパターンから生成された文字列の集合が与えられたときに，そのパターンの定数部分を見つける問題（テンプレート発見問題）として定式化する．パターンとは定数と変数からなる文字列で，パターンが生成する語は変数を定数文字列で置きかえて得られる．置きかえに用いられる文字列中の部分文字列の頻度分布はベキ分布に従うことを仮定し，高確率でテンプレート発見を解くアルゴリズムを構築する．共通部分の発見問題の1 つである最長の共通部分列を探す問題はNP 完全であることが知られているが，問題の再定式化，部分文字列の集合による定数部分の表現方法，部分文字列の頻度と総出現数から共通部分を発見する手法により，テンプレート発見問題は高確率でO(n) 時間で解けることを示す．ここで，n は入力文字列の長さの和である．さらに，このアルゴリズムがノイズに対し頑健であることと，複数のテンプレートが混在する場合でも有効であることを，Web 上の実データに適用することで実証する．

In this paper, we consider to find common parts among given strings. We define this problem as the template discovery problem which is, given a set of strings generated by some pattern, to find constant parts of the pattern. A pattern is a string over constant and variable symbols, and generates strings by replacing variables into constant strings. We assume that the frequency of replaced constant strings follows a power-law distribution, and construct an algorithm which solves the problem with high probability. Although the longest common subsequence problem, which is one of the famous common part discovery problems, is well-known to be NP-complete, we show that the template discovery problem can be solved in O(n) with high probability, where n is the total length of input strings. This complexity is achieved due to the following our contributions: reformulation of the problem, using a set of substrings to express a template, and using string frequency and all occurrences to find substrings common to input trings. Moreover, using data on the Web, we show noise robustness and effectiveness for the case that input strings are generated by different patterns.

収録刊行物

被引用文献 (2)*注記

もっと見る

参考文献 (20)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ