| Creator |
|
|
|
|
|
| Language |
|
| Publisher |
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| Publication Type |
|
| Access Rights |
|
| Related DOI |
|
| Related DOI |
|
| Related URI |
|
| Related URI |
|
| Related HDL |
|
| Relation |
|
| Abstract |
近似文字列照合問題は，二つの文字列と閾値が与えられて，片方の文字列の部分文字列のうち，もう一方の文字列との編集距離が閾値以下となるものを見つける問題である. この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムが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.show more
|
Export Mendeley
baba1