Есть ли способ оптимизировать общее регулярное выражение?

Question

Я код в Eclipse, и когда я делаю CTRL-F, чтобы найти некоторую строку, я вижу, что помимо стандартизованных опций целого слова, чувствительного к регистру, есть опция для поиска регулярных выражений (это также есть в Notepad ++) ,

Я пробовал его один или два раза, и в целом результаты почти мгновенные. Но в конце концов, файлы кода не являются большими, самые большие из них не более 500 строк, причем большинство строк заполнено менее чем наполовину. Есть ли способ оптимизировать, чтобы любое пользовательское регулярное выражение выполнялось намного быстрее на большой части текста, скажем, размером 10-15 МБ?

Я не могу придумать какой-либо метод, потому что не будет применяться стандартный алгоритм поиска, такой как Rabin-Karp, или дерево суффикса!

Answer 1

Что заставляет вас думать, что дерево суффикса не является подходящим алгоритмом для этой проблемы? От http://en.wikipedia.org/wiki/Suffix_tree:

После того, как [дерево суффикса] построено, несколько операций могут быть выполнены быстро, например, установочной подстроку в S, размещение подстроки, если определенное количество ошибок допускаются, установочных матчи за регулярным образец выражения и т. д.

Я думаю, что модифицированный алгоритм поиска строк Boyer-Moore также будет возможен.

Answer 2

Я понятия не имею, как регулярное выражение реализовано в Eclipse и почему оно так медленно. Вот только некоторые мысли:

Прежде всего, есть несколько концепций, которые вы должны знать: Nondeterministic finite automaton (NFA) и Deterministic finite automaton (DFA). Теоретически, регулярное выражение, NFA и DFA эквивалентны, что означает, что они имеют точно такую ​​же способность описывать языки (последовательности символов). Это означает, что любой из них может быть преобразован в другой (см. this site).

Регулярное выражение может быть реализовано путем преобразования его в DFA, а использование DFA для соответствия текста требует только линейного времени (многие из алгоритмов согласования строк, например KMP, являются фактически специальными DFA). Однако проблема в том, что в большинстве современных реализаций регулярных выражений появились такие функции, как обратные ссылки, что делает невозможным использование DFA.

Таким образом, если отбрасывание этих сложных функций возможно, выполнение быстрого регулярного выражения было бы осуществимым (выполните сопоставление в линейном времени). Вы можете найти больше в this article.