Java regex оптимизирует этот конкретный случай?

Question

Интересно, как работает регулярное выражение, у моего конкретного регулярного выражения есть элемент, который выглядит следующим образом:

(word1|word2|wordn......)

Количество слов большое несколько сотен .
Интересно, движок регулярных выражений просто проверяет слова одно за другим или оптимизирует поиск и каким образом.
Будет хорошим указатель на хорошую документацию.

Answer 1

Если у вас несколько сотен слов, вам нужно остерегаться порядка слов в регулярном выражении.Механизм регулярных выражений ищет слова слева направо .
Если вы проверяете слово setValue на чередование set|setValue, оно будет соответствовать только трем буквам, содержащим "набор", а невся строка.

См. эту ссылку (с www.regular-expressions.info) для полного объяснения.

Я не думаю, что механизм регулярных выражений действительнооптимизирует чередование (т. е. анализирует общие префиксы и соответственно строит nfa).Поэтому, с таким количеством слов, я не думаю, что это будет оптимизация.

Помимо переупорядочения слов, вы также можете попробовать добавить слово или границу строки после чередования, например, (set|setValue)$,но я подозреваю, что движок регулярных выражений будет выполнять много шагов назад, поэтому он может не стоить усилий.

Answer 2

Если вам кажется, что механизм RE является узким местом в таком поиске, вы можете легко сгенерировать trie и проверить на сдерживание.

Answer 3

см. эту ссылку
Эта статья о Javaworld объясняет основной механизм регулярного выражения Java (называемый NFA для недетерминированного конечного автомата, или NFA). Есть также целые книги на эту тему. Также ознакомьтесь с разделом Ресурсы .