Аноним

Последовательное точное сравнение строк: различия между версиями

Материал из WEGA

Последовательное точное сравнение строк (посмотреть исходный код)

Версия от 13:28, 29 апреля 2019

5055 байт добавлено ,  29 апреля 2019
→‎Применение
Строка 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)
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/13865