| Creator |
|
|
|
|
|
| Language |
|
| Publisher |
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Rights |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
複数の文字列に共通な部分列を見つける問題をテンプレート発見問題として定式化する．テンプ レート以外の文字列の頻度分布はベキ分布に従うことを仮定する．最長の共通部分列を探す問題はNP 完全であることが知られているが，(1) 問題の再定式化，(2) 部分文字列の集合によるテンプレート表 現，(3) 部分文字列の頻度と総出現数から共通部分を発見する手法により，テンプレート発見問題を 平均的にほぼ入力長に...線形で解くアルゴリズムを構築する．さらに，このアルゴリズムがノイズに対 し頑健であることと，複数のテンプレートが混在する場合でも有効であることを，Web 上の実データ に適用することで実証した．
We define the problem to find a subsequence common to given strings as the template discovery problem. We assume that the frequency distribution of substrings on non-template parts follows the power-law distribution. Although the longest common subsequence problem is well-known to be NP-complete, we show that the template discovery problem can be solved in almost linear in the total length 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 patternsshow more
|
Export Mendeley
2003_c_3