| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 号 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連DOI |
|
| 関連URI |
|
| 関連URI |
|
| 関連HDL |
|
| 関連情報 |
|
| 概要 |
近似文字列照合問題は，二つの文字列と閾値が与えられて，片方の文字列の部分文字列のうち，もう一方の文字列との編集距離が閾値以下となるものを見つける問題である. この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムがMyers により提案されているが，出力として編集距離だけではなくアライメントも求める場合には適用できない．本論文では，近似出現に対するアライメントについての正規形の概念を導...入し，Myers のアルゴリズムを近似文字列照合に対するアライメント問題へ拡張する
Approximate matching problem is, given two stringsand a parameter, to find all substring of a stringwhose edit distance with the other string is at mostthe parameter. Myers introduced an efficient algorithmbased on bit-parallelism for approximate matchingproblem. However, if alignment of strings is requiredas the answer of the problem, the algorithmcan not be applied straightforwardly. In this paper, an idea of normalization of alignment is introduced and the algorithm by Myers is expanded to alignment problem.続きを見る
|
Mendeley出力
