Как быстро протестировать большое количество регулярных выражений и узнать, какое из них соответствует?

Question

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

Я несколько надеялся, что будет нечто подобное для flex (быстрый лексический анализатор (не Adobe Flex)).net, который позволил бы мне указать большое количество регулярных выражений, но быстро (O (n) согласно Википедии для n = len (входная строка)) выяснить, какое регулярное выражение соответствует.

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

Answer 1

Найдите самый большой кусок постоянного текста в каждом регулярном выражении (если он превышает определенную пороговую длину) и используйте алгоритм Карпа-Рабина для одновременного поиска любой из этих строк.Для каждого совпадения запустите это регулярное выражение, чтобы увидеть, совпадает ли все это.Для каждого регулярного выражения, не включенного в многострочный поиск, выполняйте поиск по этому регулярному выражению.

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

Answer 2

Что?Даже тестирование на совпадение с одним регулярным выражением не может быть выполнено в целом за O (n) раз.Откуда вы получили эту информацию?Что это за функция во Flex?Я уверен, что это должна быть некоторая ограниченная форма регулярных выражений, а не для произвольных регулярных выражений .NET.

Для обработки произвольных регулярных выражений простой способ - сохранить ваши регулярные выражения в List и просто выполнять итерациипо каждому регулярному выражению одно за другим, пока не найдете подходящее.

Answer 3

Быстрый веб-поиск показывает, что существует лексоподобный инструмент с именем C # Lex . Но так как я не использую .NET или C #, я не могу сказать, хорошо ли это, и полезно ли это для вас.

Для Java я нашел JLex и JFlex, которые генерируют исходный код. Их использование кажется разумным только в том случае, если регулярные выражения буквально компилируются «вне сети» (вне приложения) и затем включаются в путь к классу вашего приложения. Версия .NET, вероятно, ведет себя аналогично.