Как эффективно сопоставить строку с набором подстановочных строк?

Я ищу решение для сопоставления одной строки с набором подстановочных строк. Например

>>> match("ab", ["a*", "b*", "*", "c", "*b"])
["a*", "*", "*b"]

Порядок вывода не имеет значения.

У меня будет порядка 10 ^ 4 строк с подстановочными символами для сопоставления, и я сделаю около 10 ^ 9 совпадений. Это означает, что мне, вероятно, придется переписать мой код так:

>>> matcher = prepare(["a*", "b*", "*", "c", "*b"]
>>> for line in lines: yield matcher.match("ab")
["a*", "*", "*b"]

Мы начали писать три-реализацию на Python, которая обрабатывает подстановочные знаки, и мне просто нужно правильно разобраться с этими угловыми случаями. Несмотря на это, мне любопытно услышать;Как бы вы решили это? Существуют ли какие-либо библиотеки Python, которые позволяют мне решить эту проблему быстрее?

Некоторые идеи до сих пор:

Именованные (Python, re) регулярные выражения мне здесь не помогут, так как ониЯ верну только один матч.Pyparsing похоже на классную библиотеку, но редко документируется и, на мой взгляд, не поддерживает сопоставление нескольких шаблонов.
 kreativitea16 окт. 2012 г., 00:42
Несколько вопросов. Как долго эти строки? Могут ли символы подстановки быть буквально любым символом Юникода, или это чисто?string.letters
 jfs16 окт. 2012 г., 00:34
ты имеешь ввиду10**5 струны и10**4 шаблонов, и вам нужно возвращать список подходящих шаблонов для каждой отдельной строки, или этого достаточно, чтобы вернуть один соответствующий (если он есть) шаблон для каждой строки?
 Ztyx16 окт. 2012 г., 06:59
Креативитея: Похоже, самый длинный шаблон - 980 символов. Не уверен насчет самой длинной игольной струны, но, может быть, 2000 ...
 Ztyx16 окт. 2012 г., 06:55
Я.Ф. Себастьян: На самом деле я хочу посчитать количество экземпляров каждого шаблона в огромном лог-файле.
 Joel Cornett16 окт. 2012 г., 00:43
Рассматривали ли вы использование регулярных выражений?

Ответы на вопрос(2)

Вы могли бы использоватьFilteredRE2 класс отбиблиотека re2 с помощью реализации алгоритма Aho-Corasick (или аналогичной). Отre2 документы:

Обязательные подстроки. Предположим, у вас есть эффективный способ проверить, какая из списка строк отображается в виде подстрок в большом тексте (например, возможно, вы реализовали алгоритм Aho-Corasick), но теперь ваши пользователи хотят иметь возможность выполнять поиск по регулярным выражениям также эффективно , Регулярные выражения часто содержат большие буквенные строки; если они могут быть идентифицированы, они могут быть переданы в поисковик строк, а затем результаты поисковика строк могут быть использованы для фильтрации необходимого набора поисков по регулярным выражениям. Класс FilteredRE2 реализует этот анализ. Имея список регулярных выражений, он обходит регулярные выражения для вычисления логического выражения, включающего буквенные строки, а затем возвращает список строк. Например, FilteredRE2 преобразует (привет | привет) world [a-z] + foo в логическое выражение «(helloworld ИЛИ hiworld) И Фу ” и возвращает эти три строки. При наличии нескольких регулярных выражений FilteredRE2 преобразует каждое в логическое выражение и возвращает все задействованные строки. Затем, после того, как ему сообщили, какая из строк присутствует, FilteredRE2 может оценить каждое выражение, чтобы идентифицировать набор регулярных выражений, которые могут присутствовать. Такая фильтрация может значительно сократить количество фактических поисков по регулярному выражению.

Осуществимость этих анализов в решающей степени зависит от простоты их ввода. Первый использует форму DFA, а второй использует анализируемое регулярное выражение (Regexp *). Этот вид анализа был бы более сложным (возможно, даже невозможным), если бы RE2 допускал нерегулярные функции в своих регулярных выражениях.

Похоже наАлгоритм Ахо-Корасика должно сработать.esmre кажется, делаю то, что яищу Я получил эту информацию отэтот вопрос.

Ваш ответ на вопрос