Как одновременно искать в тексте несколько регулярных выражений?

Question

[sir_Jack]

Есть N текстов и есть M регексовых выражений

Для каждого выражения надо найти тексты, соответствующие этому выражению.


M и N — достаточно большие числа, чтобы последовательно выполнять РЕГЕКС_i в ТЕКСТ_j и смотреть результат


Хочется как-то одновременно просматривать все регексы


Ну и желательно какие-нибудь модули посоветуйте, если не сложно

Comments

[sir_Jack]

Когда число регексов больше 1000 записать их через «или» как-то не слишком красиво, не так ли? Или это единственный способ?
Также очень желательно знать какой именно регекс есть в тексте

[Павел Тысляцкий]

Как я понял Вы в результате хотите получить что-то похожее на следующий результат:

{
    M1: [N1, N2, N3],
    M2: [N2, N3],
    M3: [],
    M4: [N9],
}

Спрашиваю потому что невнимательно читая можно предположить что нужны только тексты удовлетворяющие всем регэкспам.

[sir_Jack]

Да, именно так. Где-то слышал про подобные анализаторы — которые читают текст и сразу проверяют все регексы и как только какой-либо из них «сработает» — анализатор сигнализирует что сработал регекс_N и дальше либо выход, либо дальше анализировать. Только вообще не знаю что это за анализаторы

[Alukardd]

Да все равно мне кажется, что нагрузка у них не меньше чем при полном переборе или при туче ИЛИ. Так что надо выяснить что из этих 2-х вариантов быстрее и его использовать. Хотя возможно я чего-то не знаю и есть возможность существенно снизить ресурсоёмкость.

Answer 1

[Александр Давыдов]

github.com/dprokoptsev/pire

This library is aimed at checking a huge amount of text against
relatively many regular expressions.

Comments

[sir_Jack]

спасибо, это вроде бы то, что нужно… А для python нет аналогов? :)

[Александр Давыдов]

про аналоги не знаю, и питоновой обвязки к pire не нашел (

[MikhailEdoshin]

О, спасибо. Не знал, что pire это умеет, думал, это просто быстрые регулярки. Значит, есть инструмент :)

[JustAMan]

А зачем обязательно обвязка, если там простые char*? Можно же подцепить через ctypes…

Answer 2

[MikhailEdoshin]

Я не исследовал специально, но впечатление такое, что готового инструмента нет. Хотя конструкция кажется очевидной — есть M конечных автоматов (регексов), мы объединяем их в один (методы известны), плюс в начальном и/или конечном состоянии каждого исходного автомата устанавливаем callback с идентификатором этого автомата и позицией в тексте.

Может быть, взять какую-нибудь библиотеку KA и из нее что-то попытаться смастерить? Для C есть libfa (порт явовской dk.brics.automaton), первую половину задачи она выполнит, а вот помеченные состояния и callback — не знаю.

Answer 3

[Павел Тысляцкий]

Вряд ли есть готовые решения, но ведь можно делать не последовательно, а параллельно, обрабатывая в нескольких процессах/потоках, тк эти операции независимы и хорошо распараллеливаются. Если Вы еще не рассматривали этот вариант, то модуль multiprocessing думаю Вам поможет.

Если и это будет медленно, можно попробовать переписать на C.

Comments

[sir_Jack]

спасибо, можно будет подумать на эту тему

Answer 4

[Александр Коротков]

Я работаю над похожей задачей: индексный поиск по регулярным выражениям в БД. Можно вот тут почитать и презентацию посмотреть:
www.pgcon.org/2012/schedule/events/383.en.html
В применении к вашему случаю алгоритм будет такой:
1. Залить N текстов в БД.
2. Построить индекс.
3. Искать по индексу M раз.
Было интересно посмотреть, какие у вас тексты и выражения, насколько применим к этой задаче мой подход.

Comments

[sir_Jack]

Интересный подход
Я так понял индекс только для PostgreSQL?

[Александр Коротков]

Пока что да. Для метода Google Code Search есть реализация на языке go не привязанная к СУБД:
swtch.com/~rsc/regexp/regexp4.html

Answer 5

[Alukardd]

Хочется как-то одновременно просматривать все регексы

Ну так состряпайте сложный regexp с множественным ИЛИ.

Comments

[sir_Jack]

регексов очень много + нужно искать все признаки. Если регекс1 и регекс2 есть в тексте — то надо знать что это именно эти два признака

[Alukardd]

Тогда, думаю, что полный перебор (M*N) это Ваш случай.

Answer 6

[Mithgol]

Составное регулярное выражение?

Пайтона не знаю, но в джаваскрипте выглядело бы эвона как:

/(regex1|regex2|regex3|regex4|regex5|regex6|regex7|regex8|…|regexM)/

Comments

[Alukardd]

Долго писал ;-)

[sir_Jack]

их слишкм много чтобы делать через «или» + немного уточнил вопрос