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

Question

Допустим, у меня есть 10000 регулярных выражений и одна строка, и я хочу выяснить, соответствует ли строка любому из них, и получить все совпадения. Тривиальный способ сделать это - просто запросить строку один за другим для всех регулярных выражений. Есть ли более быстрый и эффективный способ сделать это?

EDIT: Я попытался заменить его DFA (лекс) Проблема здесь в том, что это даст вам только один шаблон. Если у меня есть строка "hello" и шаблоны "[H | h] ello" и ". {0,20} ello", DFA будет соответствовать только одному из них, но я хочу, чтобы они оба ударили.

Answer 1

Я сталкивался с подобной проблемой в прошлом. Я использовал решение, похожее на , предложенное akdom .

Мне повезло, что в моих регулярных выражениях обычно была подстрока, которая должна появляться в каждой строке, которой она соответствует. Мне удалось извлечь эти подстроки с помощью простого синтаксического анализатора и проиндексировать их в FSA с использованием алгоритмов Aho-Corasick. Индекс затем использовался для быстрого удаления всех регулярных выражений, которые тривиально не соответствуют заданной строке, оставляя только несколько регулярных выражений для проверки.

Я выпустил код под LGPL в виде модуля Python / C. См. esmre на хостинге с кодами Google .

Answer 2

Так работают лексеры.

Регулярные выражения преобразуются в один недетерминированный автомат (NFA) и, возможно, преобразуются в детерминированный автомат (DFA).

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

Есть много инструментов, которые могут вам здесь помочь, они называются «генератор лексеров», и есть решения, которые работают с большинством языков.

Вы не говорите, какой язык вы используете. Для программистов на Си я бы посоветовал взглянуть на инструмент re2c . Конечно, традиционный (f) lex всегда есть вариант.

Answer 3

Мы должны были сделать это на продукте, над которым я работал один раз. Ответ состоял в том, чтобы собрать все ваши регулярные выражения в Детерминированный конечный автомат (также известный как детерминированный конечный автомат или DFA ). Затем DFA может проходить символ за символом по вашей строке и запускать событие «match» всякий раз, когда совпадает одно из выражений.

Преимущества - он работает быстро (каждый символ сравнивается только один раз) и не замедляется, если вы добавляете больше выражений.

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

Тот, который мы использовали, был написан вручную в то время в нашей компании на основе шаблона C ++, поэтому, к сожалению, у меня нет никаких решений FOSS, на которые вы могли бы указать. Но если вы воспользуетесь регулярным выражением Google или регулярным выражением с помощью « DFA », вы найдете материал, который укажет вам правильное направление.

Answer 4

Martin Sulzmann Проделал немалую работу в этой области. У него есть проект HackageDB , кратко объясненный здесь , который использует частные производные , кажется, специально для этого сделан.

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

Код не основан на преобразовании в серию автоматов и последующем их объединении, вместо этого он основан на символических манипуляциях с самими регулярными выражениями.

Кроме того, код очень экспериментальный, и Мартин больше не является профессором, но занят «оплачиваемой работой» (1), поэтому может быть не заинтересован / не может предоставить какую-либо помощь или помощь.

---

1. это шутка - мне нравятся профессора, чем меньше умных пытаются работать, тем больше у меня шансов получить оплату!

Answer 5

10000 регулярных выражений, а? Предложение Эрика Венделина об иерархии кажется хорошей идеей. Думал ли ты о сокращении масштабов этих регулярных выражений до чего-то вроде древовидной структуры?

В качестве простого примера: все регулярные выражения, для которых требуется число, могут переходить от одной проверки регулярных выражений, для всех регулярных выражений, не требующих одну ветвь другой. Таким образом, вы можете уменьшить количество фактических сравнений вплоть до пути вдоль дерева вместо того, чтобы делать каждое отдельное сравнение в 10 000.

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

Если бы вам пришлось делать это во время выполнения, вы могли бы проанализировать заданные вами регулярные выражения и «подать» их либо в предопределенные жанры (проще всего), либо в сравнительные жанры, созданные в этот момент (не так просто). 1009 *

Ваш пример сравнения "hello" с "[H | h] ello" и ". {0,20} ello" на самом деле не поможет этому решению. Простой случай, когда это может быть полезно: если бы у вас было 1000 тестов, которые возвращали бы true, только если в строке есть «ello», а ваша строка теста - «до свидания»; вам нужно будет выполнить только один тест на «ello» и знать, что 1000 тестов, требующих его, не будут работать, и из-за этого вам не придется их выполнять.

Answer 6

Если вы думаете о «10000 регулярных выражениях», вам нужно изменить свои процессы мышления. Если ничего другого, подумайте с точки зрения «10000 целевых строк для сопоставления». Затем найдите методы, не относящиеся к регулярным выражениям, созданные для работы с ситуациями «загрузки целевых строк», например, машины Aho-Corasick. Честно говоря, хотя, кажется, что кое-что пошло с рельсов намного раньше в процессе, чем то, какую машину использовать, так как 10 000 целевых строк звучат намного больше как поиск в базе данных, чем как совпадение строк.

Answer 7

Вам понадобится какой-то способ определить, было ли данное регулярное выражение «аддитивным» по сравнению с другим. Создание своего рода «иерархии» регулярных выражений, позволяющей определить, что все регулярные выражения определенной ветви не совпадают

Answer 8

Вы можете объединить их в группы, может быть, по 20.

(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)

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

Если соответствие регулярному выражению regex1, группе захвата 1 будет соответствовать текст. Если нет, то это будет undefined / None / null / ...

Answer 9

Я бы сказал, что это работа для настоящего парсера. Серединой может быть грамматика выражения синтаксического анализа (PEG) . Это высокоуровневая абстракция сопоставления с образцом, одной особенностью которой является то, что вы можете определить целую грамматику вместо одного образца. Есть несколько высокопроизводительных реализаций, которые работают, скомпилировав вашу грамматику в байт-код и запустив ее на специализированной виртуальной машине.

отказ от ответственности: я знаю только одно: LPEG , библиотека для Lua , и мне было непросто (для меня) понять базовые понятия.

Answer 10

Ахо-Корасик был ответом для меня.

У меня было 2000 категорий вещей, с которыми у каждого были списки шаблонов, с которыми можно было сравнивать. Длина строки в среднем составляет около 100 000 символов.

Главное предостережение: Соответствующими шаблонами были все языковые шаблоны, а не шаблоны регулярных выражений, например. 'cat' против r'\w+'.

Я использовал Python и поэтому использовал https://pypi.python.org/pypi/pyahocorasick/.

import ahocorasick
A = ahocorasick.Automaton()

patterns = [
  [['cat','dog'],'mammals'],
  [['bass','tuna','trout'],'fish'],
  [['toad','crocodile'],'amphibians'],
]

for row in patterns:
    vals = row[0]
    for val in vals:
        A.add_word(val, (row[1], val))

A.make_automaton()

_string = 'tom loves lions tigers cats and bass'

def test():
  vals = []
  for item in A.iter(_string):
      vals.append(item)
  return vals

Выполнение %timeit test() в моих 2000 категориях с примерно 2-3 трассами на категорию и _string длиной около 100,000 заставило меня 2.09 ms против 631 ms делать последовательные re.search() 315x быстрее! .