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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если regex1 соответствует, группа захвата 1 будет иметь соответствующий текст. В противном случае это будет _2 _ / _ 3 _ / _ 4 _ / ...

Aho-Corasick был для меня ответом.

У меня было 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() в 315 раз быстрее!.

Если вы используете настоящие регулярные выражения (те, которые соответствуют регулярным языкам из теории формального языка, а не какие-то нерегулярные вещи, подобные Perl), то вам повезло, потому что регулярные языки закрыты для объединения. В большинстве языков регулярных выражений вертикальная черта (|) - это объединение. Итак, вы должны иметь возможность построить строку (представляющую желаемое регулярное выражение) следующим образом:

(r1)|(r2)|(r3)|...|(r10000)

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

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

отказ от ответственности: единственный, который я знаю, - это LPEG, библиотека для Lua, и мне было нелегко понять базовые концепции.

Я бы рекомендовал использовать Intel Hyperscan, если все, что вам нужно, это знать, какие регулярные выражения совпадают. Он построен для этой цели. Если действия, которые вам нужно предпринять, более изощренные, вы также можете использовать рагель. Хотя он создает один DFA и может привести к множеству состояний и, как следствие, очень большой исполняемой программе. Hyperscan использует гибридный подход NFA / DFA / custom для сопоставления, который хорошо обрабатывает большое количество выражений.

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

Тем не менее, похоже, что ваше решение - итеративно пробовать каждый из них - будет намного проще.

Вы можете скомпилировать регулярное выражение в гибридный DFA / автомат Букчи, где каждый раз BA переходит в состояние принятия, которое вы помечаете, какое правило регулярного выражения «сработало».

Bucchi - это немного излишне для этого, но изменение способа работы вашего DFA может помочь.

Попробуйте объединить их в одно большое регулярное выражение?

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

Короткий ответ заключается в том, что вы можете обнаружить, что ваш интерпретатор регулярных выражений уже справляется со всем этим эффективно, когда | 'd вместе, или вы можете найти тот, который работает. Если нет, то пора вам заняться поисковыми алгоритмами и поиском в Google.

Я использую Ragel с действием выхода:

action hello {...}
action ello {...}
action ello2 {...}
main := /[Hh]ello/  % hello |
        /.+ello/ % ello |
        any{0,20} "ello"  % ello2 ;

Строка «hello» вызовет код в блоке action hello, затем в блоке action ello и, наконец, в блоке action ello2.

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

Самый быстрый способ сделать это выглядит примерно так (код - C #):

public static List<Regex> FindAllMatches(string s, List<Regex> regexes)
{
    List<Regex> matches = new List<Regex>();
    foreach (Regex r in regexes)
    {
        if (r.IsMatch(string))
        {
            matches.Add(r);
        }
    }
    return matches;
}

О, вы имели в виду самый быстрый код? тогда я не знаю ....