4551
правка
Последовательное сравнение нескольких строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное сравнение нескольких строк (посмотреть исходный код)
Версия от 14:41, 6 мая 2019
, 6 мая 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 67: | Строка 67: | ||
== Применение == | == Применение == | ||
Алгоритмы решения задачи сравнения нескольких строк (MSM) служат базой для многомерного сравнения с шаблоном и приближенного сравнения с шаблоном с использованием подстановочных знаков. Эта задача часто встречается в таких областях, как вычислительная биология, поиск в базах данных, библиографический поиск, выявление вирусов в потоках данных и многие другие. | |||
== Экспериментальные результаты == | |||
Книга Наварро и Раффино [8] будет полезна для введения в данную область. В ней представлены графики экспериментов, отражающие экспериментальную оценку работы алгоритмов сравнения нескольких строк для различных значений размера алфавита, длины шаблона и размера множества шаблонов. | |||
== Ссылка на код == | |||
Эффективное решение задачи MSM обеспечивают такие хорошо известные пакеты, как agrep (http://webglimpse.net/download.html, поддиректория верхнего уровня agrep/) и grep с опцией F (http://www.gnu.org/software/grep/grep.html). | |||
== См. также == | |||
* [[Индексированное сравнение строк]] относится к случаю, при котором возможна предварительная обработка текста | |||
* [[Многомерное сравнение строк]] относится к случаю, при котором текст имеет больше одного измерения | |||
* [[Сравнение регулярных выражений]] – более сложный случай, где шаблон может быть регулярным выражением | |||
* [[Последовательное точное сравнение строк]] – версия, в которой в тексте ищется один шаблон | |||
== Литература == | |||
Дополнительную информацию можно найти в следующих книгах: [5, 6, 8] и [9]. | |||
1. Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. C. ACM 18(6), 333-340 (1975) | |||
2. 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) | |||
3. Commentz-Walter, B.: A string matching algorithm fast on the average. In: Proceedings of ICALP'79. LNCS, vol. 71, pp. 118-132. Springer, Berlin (1979) | |||
4. Crochemore, M., Czumaj, A., Gasieniec, L., Lecroq, T., Plandowski, W., Rytter, W.: Fast practical multi-pattern matching. Inf. Process. Lett. 71(3-4), 107-113 (1999) | |||
5. Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on strings. Cambridge University Press, Cambridge (2007) | |||
6. Gusfield, D.: Algorithms on strings, trees and sequences. Cambridge University Press, Cambridge (1997) | |||
7. Navarro, G., Raffinot, M.: Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM J. Exp. Algorithm 5,4 (2000) | |||
8. Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings - Practical on-line search algorithms for texts and biological sequences. Cambridge University Press, Cambridge (2002) | |||
9. Smyth, W.F.: Computing Patterns in Strings. Addison Wesley Longman (2002) | |||
10. Wu, S., Manber, U.: Agrep - a fast approximate pattern-matching tool. In: Proceedings of USENIX Winter (1992) Technical Conference, pp. 153-162. USENIX Association, Berkeley (1992) | |||
11. Wu, S., Manber, U.: A fast algorithm for multi-pattern searching. Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ (1994) | |||