logo标签列表

如何高效地将字符串与一组通配符字符串进行匹配？

python
4
我正在寻找一种解决方案，将一个字符串与一组通配符字符串进行匹配。例如：
>>> match("ab", ["a*", "b*", "*", "c", "*b"])
["a*", "*", "*b"]

输出的顺序并不重要。

我将会有大约10^4个通配符字符串需要匹配，并且我将会进行大约10^9次匹配调用。这意味着我可能需要像这样重新编写我的代码:

>>> matcher = prepare(["a*", "b*", "*", "c", "*b"]
>>> for line in lines: yield matcher.match("ab")
["a*", "*", "*b"]

我已经开始在Python中编写一个trie实现，可以处理通配符，但我需要解决一些特殊情况。尽管如此，我很想听听你的意见：你会怎么解决这个问题？有没有Python库可以让我更快地解决这个问题？ 到目前为止，一些见解如下：
  • 使用命名（Python，re）正则表达式对我没有帮助，因为它们只会返回一个匹配项。
  • pyparsing似乎是一个很棒的库，但文档稀少，而且据我所知，不支持匹配多个模式。
你的意思是有10**5个字符串和10**4个模式，需要为每个单独的字符串返回匹配的模式列表，还是仅需要为每个字符串返回一个匹配（如果有的话）的模式就足够了？ - jfs
几个问题。字符串有多长？通配符可以是任何Unicode字符，还是仅限于“string.letters”？ - kreativitea
你考虑过使用正则表达式吗？ - Joel Cornett
J.F. Sebastian：我实际上想要统计一个巨大日志文件中每个模式出现的次数。 - Ztyx
Kreativitea：看起来最长的模式是980个字符。不确定最长的针线串，但可能为2000... - Ztyx
2个回答
4
您可以使用re2库中的FilteredRE2类，并结合Aho-Corasick算法实现（或类似方法）来处理。从re2文档中得知：

所需子字符串。 假设您有一种有效的方法来检查一个大文本中的一组字符串，看哪些作为子字符串出现（例如，也许您实现了Aho-Corasick算法），但现在用户还要能够高效地进行正则表达式搜索。正则表达式通常有包含大量字面字符串；如果可以识别这些字符串，则可以将它们输入到字符串搜索器中，然后使用字符串搜索器的结果来过滤必须要进行的正则表达式搜索集合。FilteredRE2类实现了这种分析。给定一组正则表达式，它遍历正则表达式以计算涉及字面字符串的布尔表达式，然后返回该列表中的字符串。例如，FilteredRE2将(hello|hi)world[a-z]+foo转换为布尔表达式“(helloworld OR hiworld) AND foo”，并返回这三个字符串。给定多个正则表达式，FilteredRE2将每个正则表达式都转换为布尔表达式，并返回所有涉及的字符串。然后，在告诉FilteredRE2哪些字符串存在后，FilteredRE2可以评估每个表达式来确定可能存在的正则表达式集合。这种过滤可以显著减少实际正则表达式搜索的数量。

这些分析的可行性取决于其输入的简单性。第一个使用DFA形式，而第二个使用解析的正则表达式（Regexp*）。如果RE2允许在其正则表达式中包含不规则特征，则此类分析将变得更加复杂（甚至可能不可能）。

3
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接