Подтвердить что ты не робот

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

  • Это шутка - мне нравятся профессора, тем менее умные пытаются работать, тем больше у меня шансов получить деньги!

Ответ 2

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

Ответ 7

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

Ответ 8

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

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

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

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

Ответ 9

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

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

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

Ответ 10

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

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

Ответ 11

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

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

Основное предостережение. Патчи для соответствия были языковыми патчами, а не шаблонами регулярных выражений, например. 'cat' vs 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 vs 631 ms сделать последовательный re.search() 315x быстрее!.

Ответ 12

Вы можете скомпилировать регулярное выражение в гибридный DFA/Bucchi automata, где каждый раз, когда BA переходит в состояние accept, вы указываете, какое правило регулярных выражений "удар".

Bucchi немного перегружен для этого, но изменение способа работы DFA может сделать трюк.

Ответ 13

Я бы предпочел написать механизм регулярных выражений "наизнанку" - тот, где "target" был регулярным выражением, а "term" - строкой.

Тем не менее, кажется, что ваше решение попробовать каждую итеративно будет намного проще.

Ответ 14

Я использую 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.

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

Ответ 15

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

Ответ 16

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

Ответ 17

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

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

Ответ 18

Самый быстрый способ сделать это, похоже, что-то вроде этого (код С#):

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;
}

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