| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 号 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 権利関係 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
複数の文字列に共通な部分列を見つける問題をテンプレート発見問題として定式化する．テンプ レート以外の文字列の頻度分布はベキ分布に従うことを仮定する．最長の共通部分列を探す問題は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 patterns続きを見る
|
Mendeley出力
2003_c_3