我正在寻找一种将单个字符串与一组通配符字符串进行匹配的解决方案。例如
>>> 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)正则表达式在这里对我没有帮助,因为它们只会返回一个匹配项。
-
py解析 http://pyparsing.wikispaces.com/似乎是一个很棒的库,但文档很少,而且据我所知,不支持匹配多个模式。
你可以使用FilteredRE2
班级来自re2库 http://code.google.com/p/re2/在 Aho-Corasick 算法实现(或类似算法)的帮助下。从re2 docs http://swtch.com/~rsc/regexp/regexp3.html:
所需的子字符串。假设您有一种有效的方法来检查哪些
字符串列表的一个在大文本中显示为子字符串(例如
例如,也许您实现了 Aho-Corasick 算法),但现在
您的用户希望能够进行正则表达式搜索
也很有效率。正则表达式通常具有较大的文字字符串
在他们中;如果这些可以被识别出来,它们就可以被输入到
字符串搜索器,然后字符串搜索器的结果可以是
用于过滤正则表达式搜索集
必要的。 FilteredRE2 类实现了此分析。给定一个
正则表达式列表,它将正则表达式引导到
计算涉及文字字符串的布尔表达式,然后
返回字符串列表。例如,FilteredRE2 转换
(hello|hi)world[a-z]+foo 代入布尔表达式“(helloworld OR
hiworld) AND foo”并返回这三个字符串。给定多个
正则表达式,FilteredRE2 将每个转换为布尔值
表达式并返回所有涉及的字符串。然后,在被
告诉存在哪些字符串,FilteredRE2 可以评估每个字符串
表达式来标识可以的正则表达式集
可能存在。这种过滤可以减少实际的数量
正则表达式搜索显着。
这些分析的可行性关键取决于简单性
他们的投入。第一个使用 DFA 形式,而第二个使用
已解析的正则表达式 (Regexp*)。这些类型的分析将是
如果 RE2 允许非常规,那就更复杂了(甚至可能不可能)
其正则表达式的特点。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)