1294
правки
Сходство между сжатыми строками: различия между версиями
Материал из WEGA
Сходство между сжатыми строками (посмотреть исходный код)
Версия от 04:57, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия 1 участника) | |||
| Строка 114: | Строка 114: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью | Сложность задачи в наихудшем случае не вполне понятна. Для метрики самой длинной общей подпоследовательности найдены некоторые результаты с временной сложностью оптимальнее O(nm' + n'm) при вычислении сходства двух строк, закодированных при помощи длин серий [1, 11, 12]. Остается открытым вопрос о распространении этих результатов на метрику расстояния Левенштейна, метрику взвешенного расстояния редактирования и метрику аффинного штрафа за гэп. | ||
| Строка 137: | Строка 137: | ||
6. Crochemore, M., Landau, G.M.,Ziv-Ukelson, M.: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices. SIAM J. Comput. 32(6), 1654-1673 (2003) | 6. Crochemore, M., Landau, G.M.,Ziv-Ukelson, M.: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices. SIAM J. Comput. 32(6), 1654-1673 (2003) | ||
7. Fredriksson, K., Navarro, G., Ukkonen, E.: Sequential and Indexed Two-Dimensional Combinatorial Template Matching Allowing Rotations. Theor. Comput. Sci. 347(1-2), 239-275 | 7. Fredriksson, K., Navarro, G., Ukkonen, E.: Sequential and Indexed Two-Dimensional Combinatorial Template Matching Allowing Rotations. Theor. Comput. Sci. 347(1-2), 239-275(2005) | ||
(2005) | |||
[[Категория: Совместное определение связанных терминов]] | |||
8. Kim, J.W., Amir, A., Landau, G.M., Park, K.: Computing Similarity of Run-Length Encoded Strings with Affine Gap Penalty. In: Proc. 12th Symposium on String Processing and Information Retrieval (SPIRE'05). LNCS, vol. 3772, pp. 440-449 (2005) | 8. Kim, J.W., Amir, A., Landau, G.M., Park, K.: Computing Similarity of Run-Length Encoded Strings with Affine Gap Penalty. In: Proc. 12th Symposium on String Processing and Information Retrieval (SPIRE'05). LNCS, vol. 3772, pp. 440-449 (2005) | ||
