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

Question

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

你好，约翰。
今天真是美好的一天！
今天的日落很美，约翰，不是吗？
你今天会见琳达吗，约翰？

这些字符串中的大多数（不是全部）来自预定义的模式，如下所示：

“你好，%s。”
“今天真是美好的一天！”
“今天的日落很美，%s，不是吗？”
“你今天会见%s吗，%s？”

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

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

我猜该解决方案涉及从模式中构建一个正则表达式，并反复检查哪个匹配。但是，我不确定构建这些正则表达式的代码是什么样的。

注意：我在这里给出的字符串是为了说明目的。实际上，字符串不是人类生成的，而是计算机生成的人类友好的字符串，如上所示，来自我无法控制的系统。由于它们不是手动输入的，因此我们无需担心诸如拼写错误和其他人为错误之类的事情。只需要找到它匹配的模式。

注意 2：我可以将模式库修改为其他格式，如果这样可以更容易地构造正则表达式。具有 printf 样式 %s 的当前结构并不是一成不变的。

score 3 · Accepted Answer

我将其视为解析问题。这个想法是解析器函数接受一个字符串并确定它是否有效。

如果您可以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大小写。这应该在记忆中快速致盲。

score 1 · Accepted Answer

我的第一个想法是让正则表达式引擎不厌其烦地处理这个问题。它们通常经过优化以处理大量文本，因此不应该带来太多性能问题。这是蛮力，但性能似乎还可以。您可以将输入分成几部分并让多个进程处理它们。这是我经过适度测试的解决方案（在 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

score 1 · Accepted Answer

类似于 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?")

score 0 · Accepted Answer

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 的大型正则表达式，并让您的正则表达式引擎为您处理“OR”。

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

score 0 · Accepted Answer

这可能是 sscanf 的工作，在 js 中有一个实现：http: //phpjs.org/functions/sscanf/；被复制的函数是这样的：http: //php.net/manual/en/function.sscanf.php。

你应该可以在不改变准备好的琴弦的情况下使用它，但我对性能有疑问。

score 0 · Accepted Answer

我不清楚这个问题。您想从中提取模式并构建正则表达式吗？大多数正则表达式引擎都有一个“引用字符串”选项。(\Q\E)。因此，您可以将字符串设为 ^\QHi 那里，\E(?:.*)\Q.\E$ 这些将是与您想要在变量之外的字符串完全匹配的正则表达式。

如果您想使用单个正则表达式仅匹配单个模式，您可以将它们放在分组模式中以找出匹配的一个，但这不会给您每个匹配项，只是第一个匹配项。

如果您使用适当的解析器（我使用过 PEG.js），它可能更易于维护。所以如果你认为你可能会陷入正则表达式地狱，那是另一种选择

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

6 回答 6

Related

Reference