Поиск соответствия строки шаблону

Question

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

1. Привет, Джон.
2. Какой прекрасный день сегодня!
3. Прекрасный закат сегодня, Джон, не так ли?
4. Будете ли вы встречаться с Линдой сегодня, Джон?

Большинство (не все) эти строки из предопределенных шаблонов следующим образом:

1. "Привет,% S".
2. «Какой прекрасный день сегодня!»
3. «Прекрасный закат сегодня,% s, не так ли?»
4. «Встречаете ли вы% s сегодня,% s?»

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

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

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

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

Примечание 2: Я мог бы изменить библиотеку шаблонов, чтобы быть каким-то другим форматом, если это упрощает конструкцию регулярных выражений. Текущая структура с типом printf% s не установлена ​​в виде камня.

Answer 1

Моя первая мысль заключалась в том, чтобы иметь двигатель regexp, чтобы справиться с этим. Они, как правило, оптимизированы для обработки большого количества текста, поэтому это не должно быть проблемой для производительности.Это грубая сила, но производительность, похоже, в порядке. И вы можете разделить входные части на части и обработать их несколькими процессами. Вот мое умеренно протестированное решение (в Python).

import random 
import string 
import re 

def create_random_sentence(): 
    nwords = random.randint(4, 10) 
    sentence = [] 
    for i in range(nwords): 
     sentence.append("".join(random.choice(string.lowercase) for x in range(random.randint(3,10)))) 
    ret = " ".join(sentence) 
    print ret 
    return ret 



patterns = [ r"Hi there, [a-zA-Z]+.", 
      r"What a lovely day today!", 
      r"Lovely sunset today, [a-zA-Z]+, isn't it?", 
      r"Will you be meeting [a-zA-Z]+ today, [a-zA-Z]+\?"] 

for i in range(95): 
    patterns.append(create_random_sentence()) 


monster_pattern = "|".join("(%s)"%x for x in patterns) 

print monster_pattern 
print "--------------" 

monster_regexp = re.compile(monster_pattern) 

inputs = ["Hi there, John.", 
      "What a lovely day today!", 
      "Lovely sunset today, John, isn't it?", 
      "Will you be meeting Linda today, John?", 
      "Goobledigoock"]*2000 

for i in inputs: 
    ret = monster_regexp.search(i) 
    if ret: 
     print ".", 
    else: 
     print "x", 

Я создал сто моделей. Это максимальный предел библиотеки regexp python. 4 из них - ваши фактические примеры, а остальные - случайные предложения, чтобы немного подчеркнуть производительность.

Затем я объединил их в одно регулярное выражение со 100 группами. (group1)|(group2)|(group3)|.... Я предполагаю, что вам придется санировать входные данные для вещей, которые могут иметь значения в регулярных выражениях (например, ? и т. Д.). Это monster_regexp.

Тестирование одной строки против этого теста против 100 узоров за один выстрел. Существуют методы, которые извлекают точную группу, которая была сопоставлена. Я тестирую 10000 строк, 80% из которых должны совпадать, а 10% - нет. Это короткие circcuits, поэтому, если есть успех, это будет сравнительно быстро. Неудачи должны будут проходить через все регулярное выражение, чтобы оно было медленнее. Вы можете заказать вещи, основанные на частоте ввода, чтобы получить более высокую производительность.

Я запустил это на своей машине, и это мое время.

python /tmp/scratch.py 0.13s user 0.00s system 97% cpu 0.136 total

, который не так уж плохо.

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

python /tmp/scratch.py 3.76s user 0.01s system 99% cpu 3.779 total

Answer 2

Python solution. JS должен быть аналогичным.

>>> re2.compile('^ABC(.*)E$').search('ABCDE') == None 
False 
>>> re2.compile('^ABC(.*)E$').search('ABCDDDDDDE') == None 
False 
>>> re2.compile('^ABC(.*)E$').search('ABX') == None 
True 
>>> 

Трюк заключается в том, чтобы использовать^и $, чтобы связать ваш шаблон и сделать его «шаблоном». Используйте (. *) Или (. +) Или что угодно, что вы хотите «искать».

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

Если вы хотите, чтобы результат «соответствует любому шаблону соответствия», создайте массивное регулярное выражение OR и пусть ваш механизм regex обрабатывает «OR'ing для вас».

Кроме того, если у вас есть только шаблоны префикса, проверьте структуру данных TRIE.

Answer 3

Это может быть работа для sscanf, есть реализация в ЯШ: http://phpjs.org/functions/sscanf/; копия функции такова: http://php.net/manual/en/function.sscanf.php.

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

Answer 4

проблема не ясна для меня. Вы хотите взять шаблоны и выстроить регулярные выражения из него? Большинство двигателей с регулярными выражениями имеют опцию «quoted string». (\ Q \ E). Таким образом, вы можете взять строку и сделать ее ^ \ QHi там, \ E (?:. *) \ Q. \ E $ Это будут регулярные выражения, которые точно соответствуют нужной строке вне ваших переменных.

Если вы хотите использовать одно регулярное выражение для соответствия только одному шаблону, вы можете поместить их в сгруппированные шаблоны, чтобы узнать, какой из них соответствует, но это не даст вам КАЖДОЕ совпадение, только первое.

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

Answer 5

Как и решение Noufal, но возвращает совпадающий шаблон или None.

import re 

patterns = [ 
    "Hi there, %s.", 
    "What a lovely day today!", 
    "Lovely sunset today, %s, isn't it", 
    "Will you be meeting %s today, %s?" 
] 

def make_re_pattern(pattern): 
    # characters like . ? etc. have special meaning in regular expressions. 
    # Escape the string to avoid interpretting them as differently. 
    # The re.escape function escapes even %, so replacing that with XXX to avoid that. 
    p = re.escape(pattern.replace("%s", "XXX")) 
    return p.replace("XXX", "\w+") 

# Join all the pattens into a single regular expression. 
# Each pattern is enclosed in() to remember the match. 
# This will help us to find the matched pattern. 
rx = re.compile("|".join("(" + make_re_pattern(p) + ")" for p in patterns)) 

def match(s): 
    """Given an input strings, returns the matched pattern or None.""" 
    m = rx.match(s) 
    if m: 
     # Find the index of the matching group. 
     index = (i for i, group in enumerate(m.groups()) if group is not None).next() 
     return patterns[index] 

# Testing with couple of patterns 
print match("Hi there, John.") 
print match("Will you be meeting Linda today, John?") 

Answer 6

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

Строка действительна, если вы можете указать find среди заданных шаблонов.Это означает, что вам нужен индекс всех шаблонов. Индекс должен быть полным текстовым индексом. Также он должен соответствовать в соответствии с позицией слова. например. он должен быть закорочен, если первое слово ввода не найдено среди первого слова шаблонов. Он должен позаботиться о матче any, т.е. %s в шаблоне.

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

Еще лучшим решением является создание собственного индекса в формате словаря. Вот пример индекса для четырех шаблонов, которые вы указали как объект JavaScript.

{ 
    "Hi": { "there": {"%s": null}}, 
    "What: {"a": {"lovely": {"day": {"today": null}}}}, 
    "Lovely": {"sunset": {"today": {"%s": {"isnt": {"it": null}}}}}, 
    "Will": {"you": {"be": {"meeting": {"%s": {"today": {"%s": null}}}}}} 
} 

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