查找字符串是否与模式匹配

Question

在我的应用程序的某一点上,我需要在模式上匹配一些字符串.假设一些示例字符串如下所示:

1. 嗨,约翰.
2. 今天多么美好的一天!
3. 今天可爱的日落,约翰,不是吗？
4. 约翰,你今天会见琳达吗？

这些字符串中的大多数(不是全部)来自预定义的模式,如下所示:

1. "你好,%s."
2. "今天多么美好的一天!"
3. "今天可爱的日落,%s,不是吗？"
4. "你今天会见到%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