寻找一个字符串是否匹配模式

Question

在我的应用程序的某一点，我需要匹配一些模式的字符串。假设一些示例字符串如下所示：

1. 嗨，那里，约翰。
2. 今天真是美好的一天！
3. 今天可爱的日落，约翰，不是吗？
4. 约翰，你今天会和琳达见面吗？

大多数（不是全部）的这些字符串是从预先定义的模式如下：

1. “您好，％S”。
2. “今天真是美好的一天！” “今天可爱的日落，％s，不是吗？” “你今天会见％s吗，％s？”

这个模式库不断扩大（目前在1,500左右），但是手动维护。尽管（第一组）输入字符串在很大程度上是不可预知的。虽然他们中的大多数会匹配其中一种模式，但其中一些模式不会。

所以，这里是我的问题：给定一个字符串（从第一组）作为输入，我需要知道哪些模式（称为第二组）它匹配。如果没有匹配，它需要告诉我。

我猜的解决方案包括建立一个正则表达式出来的图案，并反复检查哪一个匹配。但是，我不确定构建这些正则表达式的代码是什么样的。

注：我在这里给出的字符串仅用于说明目的。实际上，这些字符串不是人类生成的，而是由我无法控制的系统在上面显示的计算机生成的人性化字符串。由于它们不是手动输入的，因此我们不需要担心类型错误和其他人为错误。只需要找到它匹配的模式。

注2：我可以修改图形库是一些其他的格式，如果这使得它更容易构建正则表达式。当前的结构与printf样式％s不同。

Answer 1

我首先想到的是具有正则表达式引擎采取的处理这一切的麻烦。它们通常被优化来处理大量的文本，所以它不应该成为性能问题。这是蛮力，但表现似乎没问题。你可以将输入分成几部分，并有多个进程处理它们。这是我经过适度测试的解决方案（使用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", 

我创建了一百个模式。这是python regexp库的最大限制。其中4个是你的实际例子，其余的都是随机句，只是为了强调一点。

然后我将它们组合成一个包含100个组的单个正则表达式。 (group1)|(group2)|(group3)|...。我猜你必须对正则表达式中的含义进行消毒处理（如?等）。这是monster_regexp。

根据此测试一个字符串在单次测试中对100个模式进行测试。有一些方法可以找出匹配的确切组。我测试了10000个字符串，其中80％应该匹配，10％不会。它缩短了成本，所以如果取得成功，它会比较快。失败将不得不贯穿整个正则表达式，所以它会变慢。您可以根据输入频率排序，以获得更多性能。

我在我的机器上运行了这个，这是我的计时。

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解决方案。 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'ing你。

此外，如果您只有前缀模式，请查看TRIE数据结构。

Answer 3

这可能是sscanf的工作，存在的js实现：http://phpjs.org/functions/sscanf/;正在复制的功能是：http://php.net/manual/en/function.sscanf.php。

您应该能够使用它没有太多的改变准备的字符串，但我对表演的疑虑。

Answer 4

这个问题我不清楚。你想采取模式，并建立正则表达式吗？ 大多数正则表达式引擎都有一个“带引号的字符串”选项。 （\ Q \ E）。所以，你可以采取的字符串，使其 ^ \ QHi那里，\ E（：*？）\问。\ E $这将是正是你想要的变量外的字符串相匹配的正则表达式。

如果你想使用一个正则表达式来匹配一个模式，你可以把它们放在分组模式中找出哪一个匹配，但不会给你每一个匹配，只是第一个匹配。

如果您使用合适解析器（我用PEG.js），它可能是更容易维护，但。所以这是另一种选择，如果你认为你可能会停留在正则表达式地狱

Answer 5

类似Noufal的解决方案，但返回匹配的模式或无。

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的情况。这应该在记忆中快速致盲。