logo标签列表

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

regexnode.jspattern-matching
6
在我的应用程序中，我需要将一些字符串与模式匹配。假设其中一些示例字符串如下所示：
1. Hi there, John. 2. What a lovely day today! 3. Lovely sunset today, John, isn't it? 4. Will you be meeting Linda today, John?
大多数（不是全部）这些字符串来自预定义的模式，如下所示：
1. "Hi there, %s." 2. "What a lovely day today!" 3. "Lovely sunset today, %s, isn't it?" 4. "Will you be meeting %s today, %s?"
此模式库正在不断扩大（当前约为1,500个），但需要手动维护。然而，输入字符串（第一组）主要是不可预测的。虽然它们中的大多数将与其中一个模式匹配，但其中一些可能不匹配任何模式。
因此，我的问题是：给定一个字符串（来自第一组）作为输入，我需要知道它匹配了哪个模式（第二组）。如果没有匹配的内容，需要告诉我。
我猜解决方案涉及构建模式的正则表达式，并循环检查哪个匹配。但是，我不确定构建这些正则表达式的代码是什么样子的。
请注意：这里给出的字符串仅用于说明目的。实际上，这些字符串不是人工生成的，而是计算机生成的类似于上面的人类友好字符串，来自我不能控制的系统。由于它们不是手动键入的，我们不需要担心诸如拼写错误和其他人为错误之类的问题。只需找到它匹配的模式即可。
请注意2：如果更改模式库以使其更易于构造正则表达式，则可以采用其他格式。目前的结构，使用printf样式的%s，不是定死的。
请求的性能是什么？在1500个字符串上使用正则表达式可能不是最快的事情...您可以从匹配一些字符开始，也许只是第一个（不包括空格），然后再传递给正则表达式。 - lunadir
@lunadir 性能必须是顶尖的。我需要每秒处理约6000个这样的字符串，但我可以使用多个进程。我一开始没有考虑性能，因为我想先有一个最基本的工作解决方案。 - Rakesh Pai
@lunadir 另外，它不需要是一个正则表达式。它可以是1500个不同的正则表达式，以及一些if/else语句，在JS中运行在预生成的函数内（由new Function创建），如果这有助于获得更好的性能。 - Rakesh Pai
输入与预先制作的字符串的粘合度应该有多严格？只需要最低限度吗？逐字逐句？甚至包括空格和逗号？ - lunadir
@lunadir 我现在不确定宽松程度会如何影响匹配的质量，所以我会选择“非常严格”。但我并不完全确定。 - Rakesh Pai
6个回答
3
我将这看作一个解析问题。想法是解析函数接受字符串并确定它是否有效。
如果您可以在给定的模式中找到字符串，则该字符串有效。这意味着您需要所有模式的索引。索引必须是完整的文本索引。还必须根据单词位置匹配。例如，如果输入的第一个单词未在模式的第一个单词中找到，则应立即停止匹配。它应该处理任何匹配，即模式中的 %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}}}}}}
}

这个索引根据单词位置递归下降。因此，搜索第一个单词，如果找到，则在第一个返回的对象中搜索下一个单词，以此类推。同一级别的相同单词将只有一个键。您还应匹配任何情况。这在内存中应该非常快。

这是一个非常有趣的方法 - 特别是递归下降索引。谢谢。我会试一试的。 - Rakesh Pai
这是一棵后缀树，每条边都标有单词（而不是通常情况下的字母）。很好。 - Noufal Ibrahim
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个组的单个regexp。(group1)|(group2)|(group3)|...。我猜您将不得不对可以在正则表达式中具有含义的内容进行输入清理（例如?等）。那就是monster_regexp。
对此字符串进行测试，可以在一次操作中测试100个模式。有一些方法可以获取匹配的确切组。我测试了10000个字符串，其中80%应该匹配，10%不匹配。它会短路，所以如果成功，它将比较快。失败将不得不运行整个regexp，因此它将更慢。您可以根据输入的频率对事物进行排序，以获得更多的性能。
我在我的计算机上运行了这个程序，这是我的时间。 python /tmp/scratch.py 0.13s user 0.00s system 97% cpu 0.136 total 这还不错。
然而，对于如此大的正则表达式运行模式并失败将需要更长时间，因此我更改了输入，使用大量随机生成的不匹配字符串进行尝试。 10000个字符串都不匹配monster_regexp，我得到了这个结果。

python /tmp/scratch.py 3.76秒 用户0.01秒 系统99% CPU 3.779 总计

“失败将不得不运行整个正则表达式，因此速度会变慢。” -- 为什么？ - Anand Chitipothu
你应该使用match而不是search，对吗？ - Anand Chitipothu
我的猜测是，如果一个字符串能够快速匹配正则表达式，它将返回匹配结果；但如果必须在整个正则表达式中查找才能确定没有匹配项，那么这将需要更长的时间。 - Noufal Ibrahim
接受这个，因为它是最接近我所选择的。谢谢你，Noufal！你太棒了！ - Rakesh Pai
1
与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?")
我想到的另一件事是使用命名组而不是常规组，这样您就可以使用groupdict方法来挑选出确切匹配的组，而不是遍历100个奇怪的组以挑选出非“None”值。 - Noufal Ibrahim
0

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数据结构。

0
0

问题对我来说不太清楚。您想将这些模式构建为正则表达式吗？ 大多数正则表达式引擎都有“引用字符串”选项（\Q \E）。因此，您可以将字符串采用以下格式 ^\QHi there,\E(?:.*)\Q.\E$ 这些将是正则表达式，与您的变量之外完全匹配所需的字符串。

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

如果您使用正确的解析器（我使用过PEG.js），则可能更易于维护。因此，如果您认为您可能陷入正则表达式地狱，则还有另一种选择。

谢谢。澄清一下，只有一个模式会匹配。解决方案不必是一个巨大的正则表达式。感谢提醒关于引用字符串和PEG.js的问题。我会看一下的。 - Rakesh Pai
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接