Эффективный запрос одной строки к нескольким регулярным выражениям
Допустим, у меня есть 10000 регулярных выражений и одна строка, и я хочу выяснить, соответствует ли строка любому из них, и получить все совпадения. Тривиальный способ сделать это - просто запросить строку один за другим для всех регулярных выражений. Есть ли более быстрый и эффективный способ сделать это?
РЕДАКТИРОВАТЬ: Я пытался заменить его DFA (лекс). Проблема в том, что он даст вам только один шаблон. Если у меня есть строка "hello" и шаблоны "[H|h]ello" и ".{0,20}ello", DFA будет соответствовать только одному из них, но я хочу, чтобы они оба поразили.
17 ответов
Martin Sulzmann Проделал немалую работу в этой области. Здесь он кратко объяснил проект HackageDB, который использует частные производные, похоже, специально для этого.
Используемый язык - Haskell, и поэтому будет очень трудно перевести его на нефункциональный язык, если это будет желание (я думаю, что перевод на многие другие языки FP все еще будет довольно сложным).
Код не основан на преобразовании в серию автоматов и последующем их объединении, вместо этого он основан на символических манипуляциях с самими регулярными выражениями.
Кроме того, кодекс очень экспериментален, и Мартин больше не является профессором, но работает на "оплачиваемую работу" (1), поэтому может быть не заинтересован / не может оказать какую-либо помощь или помощь.
- это шутка - мне нравятся профессора, чем меньше умных пытаются работать, тем больше у меня шансов получить оплату!
Так работают лексеры.
Регулярные выражения преобразуются в один недетерминированный автомат (NFA) и, возможно, преобразуются в детерминированный автомат (DFA).
Получившийся автомат попытается сопоставить все регулярные выражения сразу и преуспеет в одном из них.
Здесь есть много инструментов, которые могут вам помочь, они называются "генератор лексеров", и есть решения, которые работают с большинством языков.
Вы не говорите, какой язык вы используете. Для программистов на C я бы посоветовал взглянуть на инструмент re2c. Конечно, традиционный (f)lex - это всегда вариант.
Я сталкивался с подобной проблемой в прошлом. Я использовал решение, похожее на предложенное Акдом.
Мне повезло, что в моих регулярных выражениях обычно была подстрока, которая должна появляться в каждой строке, которой она соответствует. Мне удалось извлечь эти подстроки с помощью простого парсера и проиндексировать их в FSA с использованием алгоритмов Aho-Corasick. Индекс затем использовался для быстрого удаления всех регулярных выражений, которые тривиально не соответствуют заданной строке, оставляя только несколько регулярных выражений для проверки.
Я выпустил код под LGPL в виде модуля Python/C. Смотрите esmre на Google code hosting.
Мы должны были сделать это на продукте, над которым я работал один раз. Ответ состоял в том, чтобы собрать все ваши регулярные выражения в детерминированный конечный автомат (также известный как детерминированный конечный автомат или DFA). Затем DFA может проходить символ за символом по вашей строке и запускать событие "match" всякий раз, когда выполняется совпадение одного из выражений.
Преимущества в том, что он работает быстро (каждый символ сравнивается только один раз) и не становится медленнее, если вы добавляете больше выражений.
Недостатки в том, что для автомата требуется огромная таблица данных, и существует много типов регулярных выражений, которые не поддерживаются (например, обратные ссылки).
Тот, который мы использовали, был написан вручную в нашей компании в то время, как шаблон C++, поэтому, к сожалению, у меня нет решений FOSS, на которые вы могли бы указать. Но если вы воспользуетесь регулярным выражением Google или регулярным выражением с помощью "DFA", вы найдете материал, который укажет вам правильное направление.
10 000 регулярных выражений, а? Предложение Эрика Венделина об иерархии кажется хорошей идеей. Думали ли вы о том, чтобы уменьшить грандиозность этих регулярных выражений до чего-то вроде древовидной структуры?
В качестве простого примера: все регулярные выражения, требующие числа, могут разветвляться от одного регулярного выражения, проверяя это, все регулярные выражения, не требующие одну ветвь другой. Таким образом, вы можете уменьшить количество фактических сравнений вплоть до пути вдоль дерева вместо того, чтобы делать каждое отдельное сравнение в 10000.
Это потребовало бы разложения регулярного выражения, предоставляемого по жанрам, причем каждый жанр имел общий тест, который исключал бы их в случае неудачи. Таким образом, вы можете теоретически значительно сократить количество фактических сравнений.
Если вам нужно было сделать это во время выполнения, вы могли бы проанализировать заданные вами регулярные выражения и "подать" их либо в предопределенные жанры (проще всего), либо в сравнительные жанры, сгенерированные в этот момент (не так просто сделать).
Ваш пример сравнения "привет" с "[H|h]ello" и ".{0,20}ello" не поможет в этом решении. Простой случай, когда это может быть полезно: если бы у вас было 1000 тестов, которые вернули бы true, только если в строке есть "ello", а ваша строка теста - "до свидания"; вам нужно будет только выполнить один тест на "ello" и знать, что 1000 тестов, требующих его, не будут работать, и из-за этого вам не придется их выполнять.
Если вы думаете о "10 000 регулярных выражений", вам нужно изменить свои процессы. Если ничего другого, подумайте с точки зрения "10000 целевых строк, чтобы соответствовать". Затем ищите методы, не относящиеся к регулярным выражениям, созданные для работы с ситуациями "загрузки целевых строк", например, машины Aho-Corasick. Честно говоря, похоже, что кое-что пошло с рельсов гораздо раньше в процессе, чем то, какую машину использовать, так как 10 000 целевых строк звучат гораздо больше как поиск в базе данных, чем как совпадение строк.
Вам нужно было бы каким-то образом определить, было ли данное регулярное выражение "аддитивным" по сравнению с другим. Создание своего рода "иерархии" регулярных выражений, позволяющей определить, что все регулярные выражения определенной ветви не совпадают
Ахо-Корасик был ответом для меня.
У меня было 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 раз быстрее!,
Вы можете объединить их в группы, возможно, по 20 человек.
(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)
Пока у каждого регулярного выражения есть ноль (или, по крайней мере, одинаковое количество) групп захвата, вы можете посмотреть, что захватили, чтобы увидеть, какой шаблон (ы) совпал.
Если соответствие regex1, группе захвата 1 будет соответствовать текст. Если нет, то это будет undefined/None/null/...
Если вы используете настоящие регулярные выражения (те, которые соответствуют регулярным языкам из теории формальных языков, а не каким-то нерегулярным Perl-вещам), то вам повезло, потому что регулярные языки закрыты при объединении. В большинстве языков регулярных выражений pipe (|) - это union. Таким образом, вы должны иметь возможность построить строку (представляющую нужное вам регулярное выражение) следующим образом:
(r1)|(r2)|(r3)|...|(r10000)
где скобки для группировки, не совпадают. Все, что соответствует этому регулярному выражению, соответствует по крайней мере одному из ваших исходных регулярных выражений.
Я бы рекомендовал использовать Intel Hyperscan, если все, что вам нужно, это знать, какие регулярные выражения совпадают. Он создан для этой цели. Если действия, которые вам нужно предпринять, более изощренные, вы также можете использовать рагель. Хотя он создает один DFA и может привести к множеству состояний и, как следствие, очень большой исполняемой программе. Hyperscan использует гибридный подход NFA/DFA/custom для сопоставления, который хорошо обрабатывает большое количество выражений.
Я бы сказал, что это работа для настоящего парсера. Серединой может быть грамматика синтаксического анализа (PEG). Это высокоуровневая абстракция сопоставления с образцом, одной особенностью которой является то, что вы можете определить целую грамматику вместо одного образца. Есть несколько высокопроизводительных реализаций, которые работают путем компиляции вашей грамматики в байт-код и запуска ее в специализированной виртуальной машине.
Отказ от ответственности: я знаю только LPEG, библиотеку для Lua, и мне было нелегко понять базовые концепции.
Я бы почти предложил написать движок регулярных выражений "наизнанку" - тот, в котором "target" - это regex, а "term" - строка.
Однако, кажется, что ваше решение попробовать каждый из них итеративно будет намного проще.
Я использую Ragel с уходящим действием:
action hello {...}
action ello {...}
action ello2 {...}
main := /[Hh]ello/ % hello |
/.+ello/ % ello |
any{0,20} "ello" % ello2 ;
Строка "привет" будет вызывать код в 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;
}
О, ты имел в виду самый быстрый код? тогда я не знаю....
Попробуйте объединить их в одно большое регулярное выражение?
Я думаю, что короткий ответ: да, есть способ сделать это, и это хорошо известно информатике, и я не могу вспомнить, что это такое.
Короткий ответ: вы можете обнаружить, что ваш интерпретатор регулярных выражений уже эффективно справляется со всем этим, когда вы вместе, или вы можете найти того, кто это делает. Если нет, то пришло время для Google поиска строк и алгоритмов поиска.