4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 89: | Строка 89: | ||
== Применение == | == Применение == | ||
Описанные выше методы применимы к обработке естественного языка, обработке и анализу генетических и музыкальных последовательностей, задачам безопасности применительно к потокам данных, таким как выявление вирусов, а также управлению текстовыми базами данных и множеству других областей. | |||
== Открытые вопросы == | |||
В этой сфере остается не так уж много нерешенных задач. Все еще неизвестно, возможно ли разработать алгоритм сравнения строк с оптимальным в среднем случае временем выполнения и константным объемом требуемой памяти. Также до сих пор неизвестен точный размер конечного автомата Бойера-Мура [5]. | |||
== Экспериментальные результаты == | |||
Книга Наварро и Раффино [12] может служить подходящим введением в проблему, в ней также представлена экспериментальная карта алгоритмов ESM для разных значений размера алфавита и длины шаблона. В частности, алгоритм сдвига Shift-Or эффективен для небольших алфавитов и коротких шаблонов, BNDM – для алфавитов и шаблонов среднего размера, алгоритм Хорспула – для больших алфавитов, а BOM – для длинных шаблонов. | |||
== Ссылка на код == | |||
На сайте monge.univ-mlv.fr/~lecroq/string представлено большое количество алгоритмов для решения задачи ESM (см. также [2]). Каждый алгоритм реализован на языке C и снабжен Java-апплетом. | |||
== См. также == | |||
* [[Индексированное приближенное сравнение строк]] относится к случаю, при котором выполняется предварительная обработка текста. | |||
* [[Сравнение регулярных выражений]] – более сложный случай, где P может быть регулярным выражением. | |||
* [[Последовательное точное сравнение строк]] – версия, в которой ошибки не допускаются. | |||
* [[Последовательное точное сравнение нескольких строк]] – версия, в которой в тексте ищется конечное множество шаблонов. | |||
== Литература == | |||
1. Allauzen, C., Crochemore, M., Raffinot, M.: Factor oracle: a new structure for pattern matching. In: SOFSEM'99. LNCS, vol. 1725, pp. 291-306. Springer, Berlin (1999) | |||
2. Charras, C., Lecroq, T.: Handbook of exact string matching algorithms. King's College London Publications, London (2004) | |||
3. Cole, R., Hariharan, R., Paterson, M., Zwick, U.: Tighter lower bounds on the exact complexity of string matching. SIAM J. Comput. 24(1), 30-45 (1995) | |||
4. Crochemore, M., Czumaj, A., G^sieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string matching algorithms. Algorithmica 12(4/5), 247-267 (1994) | |||
5. Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press, New York (2007) | |||
6. Crochemore, M., Perrin, D.: Two-way string matching. J. ACM 38(3),651-675(1991) | |||
7. Fredriksson, K., Grabowski, S.: Practical and optimal string matching. In: Proceedings of SPIRE'2005. LNCS, vol. 3772, pp. 374-385. Springer, Berlin (2005) | |||
8. Galil, Z., Seiferas, J.: Time-space optimal string matching. J. Comput. Syst. Sci. 26(3), 280-294 (1983) | |||
9. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge, UK (1997) | |||
10. Hancart, C.: On Simon's string searching algorithm. Inf. Process. Lett. 47(2), 95-99 (1993) | |||
11. Knuth, D.E., Morris, J.H. Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(1), 323-350 (1977) | |||
12. Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge, Uk (2002) | |||
13. Rytter, W.: On maximal suffixes and constant-space linear-time versions of KMP algorithm. Theor. Comput. Sci. 299(1-3), 763-774 (2003) | |||
14. Smyth, W.F.: Computing Patterns in Strings. Addison Wesley Longman, Harlow, UK (2002) | |||
15. Yao, A.: The complexity of pattern matching for a random string. SIAM J. Comput. 8,368-387 (1979) |
правка