| Abstract |
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 consta...nt 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 strings. Moreover, using data on the Web, we show noise robustness and effectiveness for the case that input strings are generated by different patterns.
本論文では,複数の文字列に共通な部分を見つける問題を考察する.まず,この問題をパターンから生成された文字列の集合が与えられたときに,そのパターンの定数部分を見つける問題(テンプレート発見問題)として定式化する.パターンとは定数と変数からなる文字列で,パターンが生成する語は変数を定数文字列で置きかえて得られる.置きかえに用いられる文字列中の部分文字列の頻度分布はベキ分布に従うことを仮定し,高確率でテンプレート発見を解くアルゴリズムを構築する.共通部分の発見問題の1つである最長の共通部分列を探す問題はNP完全であることが知られているが,問題の再定式化,部分文字列の集合による定数部分の表現方法,部分文字列の頻度と総出現数から共通部分を発見する手法により,テンプレート発見問題は高確率で0(n)時間で解けることを示す.ここで,nは入力文字列の長さの和である.さらに,このアルゴリズムがノイズに対し頑健であることと,複数のテンプレートが混在する場合でも有効であることを,Web上の実データに適用することで実証する.show more
|
Export Mendeley
hirokawa_220