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似乎是一个很棒的库，但是文档很少，而且在我看来，它不支持匹配多个模式。
4

2 回答 2

4

您可以在 Aho-Corasick 算法实现（或类似算法）的帮助下使用re2 库FilteredRE2中的类。来自re2 文档：

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

这些分析的可行性主要取决于其输入的简单性。第一个使用 DFA 形式，而第二个使用已解析的正则表达式 (Regexp*)。如果 RE2 在其正则表达式中允许非正则特征，这种分析会更加复杂（甚至可能是不可能的）。

于 2012-10-22T05:09:49.293 回答
3

似乎Aho-Corasick 算法会起作用。esmre似乎在做我正在寻找的东西。我从这个问题中得到了这个信息。

于 2012-10-15T22:21:44.553 回答