Оптимизация производительности поисковой системы .NET RegExp

Question

У меня есть список коллекции с около 35 000 строк

Типичная строка выглядит так:

"<i>füüs</i>ampri tähis;lüh ld-st<i>anno</i>, aastal;<i>maj</i> lüh pr-st<i>argent</i>, raha (kursisedelitel)"

В основном эта строка содержит несколько слов на эстонском языке:)

Мне нужно разрешить пользователю выполнять поиск RegExp по 35 000 строк

Если я выполняю поиск с использованием выражения /ab.*/, поиск занимает менее секунды

Если я выполняю поиск по выражению /.*ab/, поиск занимает около 10 секунд

Мой вопрос: как я могу ускорить второй поиск (менее 1,5 секунд)?

Большое спасибо

Answer 1

То, как обрабатываются регулярные выражения, делает их такими разными. Чтобы объяснить это на основе ваших примеров:

• /.*ab/ Это выражение состоит из двух подвыражений: .* и литерала ab. Это будет обработано следующим образом: В обычном жадном режиме, где каждый квантор и, следовательно, соответствие расширяется до своего максимума, .* сначала будет соответствовать всей строке. Затем он попытается сопоставить следующее ab. Но так как это невозможно (мы уже находимся в конце строки), обратный путь будет использоваться для поиска последней точки, где оба подвыражения совпадают. Таким образом, совпадение .* уменьшается на один символ и снова проверяется ab. Если все выражение не может быть сопоставлено, совпадение .* снова будет уменьшено на один символ, пока не будет сопоставлено все выражение. В худшем случае в строке нет ab, и алгоритм выполнит n + 1 возвратов и дополнительные тесты для ab, пока не обнаружит, что совпадение невозможно.

• /ab.*/ Это выражение также состоит из двух подвыражений. Но здесь порядок меняется, сначала литерал ab, а затем .*. Это обрабатывается следующим образом: алгоритм сначала пытается найти литерал ab, сравнивая один символ с другим. Если есть совпадение, он пытается найти совпадение для .*, что очевидно просто.

Основное различие между этими двумя регулярными выражениями состоит в том, что второе имеет статическую часть в начале и переменную часть в конце. Это не требует возврата.

Попробуйте воспользоваться инструментом анализа регулярных выражений, например RegexBuddy , чтобы увидеть разницу визуально.

Answer 2

Используйте скомпилированные регулярные выражения для лучшей производительности

http://en.csharp -online.net / CSharp_Regular_Expression_Recipes -Compiling_Regular_Expressions

copy вставьте полный URL, похоже, что с этой ссылкой возникла проблема с рендерингом.

Answer 3

Существуют две возможные модификации, которые я могу предложить для медленного выражения .*ab.

Я выполнил свои тесты с этой тестовой строкой "1234567890 ab 1234567890", используя функцию сравнения в Regex Hero.

A . В 5 раз быстрее, чем оригинал

^.*ab
RegexOptions.None

или

B . В 8 раз быстрее, чем оригинал

.*ab
RegexOptions.RightToLeft

Иногда эксперименты окупаются. RightToLeft вариант был моим "ах!" момент. По сути, это возвращает ту же производительность, что и ваше другое выражение ab.*, предотвращая когда-либо массовый возврат.

Answer 4

Ваше второе выражение будет соответствовать 'ab' и всем символам перед ним (кроме новой строки). Вы можете попробовать поискать только / ab /, получить индекс совпадения и в результате сопоставить ту часть строки, которая предшествует совпадению с совпадением.

Answer 5

Мне пришла в голову эта сумасшедшая идея, что вы можете также хранить строки в обратном порядке и искать эти строки с помощью /ba.*/, если пользователь введет /.*ab/.