Алгоритм для множественного расширенного соответствия строк

Question

Мне нужно реализовать алгоритм для множественного расширенного соответствия строк в тексте.

Расширенная означает наличие подстановочных знаков (любое количество символов вместо звезды), например:

abc*def //matches abcdef, abcpppppdef etc. 

Множественные означает, что поиск происходит одновременно для нескольких моделей струнных (не отдельный поиск для каждого шаблона), например:

abc*def 
abc 
whatever 
some*string 

ВОПРОС:

Что такое быстрый алгоритм, который может выполнять множественное расширенное сопоставление строк?

Предпочтительно оптимизирован для SIMD-инструкций и многоядерной реализации. Реализация с открытым исходным кодом (C/C++/Python) также будет отличной.

Спасибо

Answer 1

Я думаю, что это может иметь смысл начать с чтения раздела в следующей статье Википедии: http://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times. Затем вы можете выполнить обзор литературы по алгоритмам, реализуя соответствие шаблону регулярного выражения .

С точки зрения практической реализации , существует большое разнообразие регулярное выражение (регулярное выражение) двигателей в виде библиотек, сфокусированные на одном или нескольких языках программирования. Скорее всего, лучшим и самым популярным вариантом является C/C++ PCRE library с его новейшей версией PCRE2, выпущенной в 2015 году. Другая библиотека регулярных выражений C++, которая довольно популярна в Google, - RE2. Я рекомендую вам прочитать this paper вместе с двумя другими, связанными в статье, для получения подробной информации об алгоритмах, реализации и контрольных показателях. Совсем недавно Google выпустил RE2/J - линейную временную версию RE2 для Java: подробнее см. this blog post. Наконец, я столкнулся с интересной чистой библиотекой C regex TRE, которая предлагает слишком много интересных функций, которые перечислены здесь. Тем не менее, вы можете прочитать о них все на this page.

P.S. Если этого недостаточно, вы можете посетить this Wikipedia page для получения подробной информации о многих других машинах и библиотеках regex и их сравнении по нескольким критериям. Надеюсь, мой ответ поможет.