4551
правка
Последовательное приближенное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное приближенное сравнение строк (посмотреть исходный код)
Версия от 16:57, 29 марта 2019
, 29 марта 2019→Экспериментальные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 88: | Строка 88: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Исчерпывающий обзор материалов по данному вопросу [11] включает множество экспериментов. На сегодняшний день самыми быстрыми алгоритмами для расстояния редактирования на практике являются алгоритмы фильтрации [6, 12] в сочетании с битово-параллельными алгоритмами для проверки областей-кандидатов [2, 10]. Эти алгоритмы фильтрации хорошо работают для достаточно малых значений k/m, в противном случае битово-параллельные алгоритмы следует использовать автономно. Алгоритмы фильтрации легко допускают расширение с целью поддержки поиска по нескольким образцам одновременно. | |||
== Ссылка на код == | |||
Эффективное решение задачи ASM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и nrgrep (http://www.dcc.uchile.cl/~gnavarro/software). | |||
== См. также == | |||
* [[Приближенное сравнение регулярных выражений – более сложный случай, где P может быть регулярным выражением]] | |||
* [[Индексированное приближенное сравнение строк относится к случаю, при котором возможна предварительная обработка текста]] | |||
* [[Локальное выравнивание (с вогнутыми штрафами за пропуски) относится к более сложной схеме с весами, представляющей интерес для вычислительной биологии]] | |||
* [[Последовательное точное сравнение строк – упрощенная версия, в которой ошибки не допускаются]] | |||
== Литература == | |||
1. Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms 50(2), 257-275 | |||
(2004) | |||
2. Baeza-Yates, R., Navarro, G.: Faster approximate string matching. Algorithmica 23(2), 127-158 (1999) | |||
3. Chang, W., Marr, T.: Approximate string matching and local similarity. In: Proc. 5th Annual Symposium on Combinatorial Pattern Matching (CPM'94). LNCS, vol. 807, pp. 259-273. Springer, Berlin, Germany (1994) | |||
4. Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. SIAM J. Comput. 31 (6), 1761 -1782 (2002) | |||
5. Crochemore, M., Landau, G., Ziv-Ukelson, M.: A subquadratic sequence alignment algorithm for unrestricted scoring matrices. SIAM J. Comput. 32(6), 1654-1673 (2003) | |||
6. Fredriksson, K., Navarro, G.: Average-optimal single and multiple approximate string matching. ACM J. Exp. Algorithms 9(1.4)(2004) | |||
7. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge (1997) | |||
8. Landau, G., Vishkin, U.: Fast parallel and serial approximate string matching. J. Algorithms 10,157-169 (1989) | |||
9. Masek, W., Paterson, M.: A faster algorithm for computing string edit distances. J. Comput. Syst. Sci.20,18-31 (1980) | |||
10. Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic progamming. J. ACM 46(3), 395-415(1999) | |||
11. Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31-88(2001) | |||
12. Navarro, G., Baeza-Yates, R.: Very fast and simple approximate string matching. Inf. Proc. Lett. 72,65-70 (1999) | |||
13. Sellers, P.: The theory and computation of evolutionary distances: pattern recognition. J. Algorithms 1, 359-373 (1980) | |||
14. Ukkonen, E.: Finding approximate patterns in strings. J. Algorithms 6,132-137 (1985) | |||
15. Yao, A.: The complexity of pattern matching for a random string. SIAM J. Comput. 8,368-387 (1979) | |||