编辑: 我尝试使用DFA(lex)进行替换 这里的问题是它只会给您一个单一的模式。如果我有一个字符串“hello”和模式“[H|h]ello”和“.{0,20}ello”,DFA只会匹配其中一个,但我希望两个都匹配上。
我曾经遇到过类似的问题。我使用了与akdom建议的解决方案类似的解决方案。
我很幸运,因为我的正则表达式通常都有一些子字符串,这些子字符串必须出现在它所匹配的每个字符串中。我能够使用一个简单的解析器提取这些子字符串,并使用Aho-Corasick算法将它们索引到FSA中。然后使用该索引快速消除所有在给定字符串上无法匹配的正则表达式,只留下少数几个需要检查的正则表达式。
我以Python/C模块的形式在LGPL下发布了这些代码。请参见Google代码托管上的esmre。
Martin Sulzmann在这个领域做了很多工作。他有一个HackageDB项目,简要说明可以在这里找到,其中使用部分导数似乎是为此量身定制的。
所使用的语言是Haskell,并且如果需要转换为非函数式语言,则将非常困难(我认为转换为许多其他FP语言仍然会非常困难)。
代码不是基于将正则表达式转换为一系列自动机,然后将它们组合起来,而是基于对正则表达式本身进行符号操作。
此外,代码非常实验性,Martin不再是教授,但已经有“盈利就业”(1),因此可能不感兴趣或无法提供任何帮助或输入。
有10,000个正则表达式?Eric Wendelin建议使用层次结构,这似乎是个好主意。你是否考虑将这些正则表达式的数量减少到类似于树形结构的形式?
举个简单的例子:所有需要数字的正则表达式可以从一个检查数字的正则表达式分支出来,不需要数字的则从另一个分支出来。通过这种方式,您可以将实际比较的数量减少到树上的路径,而不是在10,000个正则表达式中进行每一个比较。
这将需要将提供的正则表达式分解成流派,每个流派都有一个共享测试,如果测试失败,则会排除它们。通过这种方式,您可以理论上大大减少实际比较的数量。
如果您必须在运行时执行此操作,则可以解析给定的正则表达式并将其“归档”到预定义的流派(最容易做到)或在那一刻生成的比较流派(不太容易做到)中。
您比较"hello"和"[H|h]ello"以及".{0,20}ello"的例子不会受到此解决方案的帮助。这种解决方案有用的一个简单情况是:如果您有1000个测试,只有在字符串中存在"ello"时才返回true,并且您的测试字符串是"goodbye;",那么您只需要进行一次关于"ello"的测试,就知道需要它的1000个测试不起作用,因此您不必执行它们。
import ahocorasick
A = ahocorasick.Automaton()
patterns = [
[['cat','dog'],'mammals'],
[['bass','tuna','trout'],'fish'],
[['toad','crocodile'],'amphibians'],
]
for row in patterns:
vals = row[0]
for val in vals:
A.add_word(val, (row[1], val))
A.make_automaton()
_string = 'tom loves lions tigers cats and bass'
def test():
vals = []
for item in A.iter(_string):
vals.append(item)
return vals
在我的2000个类别中,每个类别大约有2-3个跟踪项,并且_string长度约为100,000,在其中运行%timeit test()
,我得到了2.09毫秒
的结果,而使用顺序的re.search()
则需要631毫秒
,速度提升了315倍!
你需要有一种方法来确定给定的正则表达式是否与另一个正则表达式“加法”相比。 创建一种正则表达式的“等级制度”,使您能够确定某个分支的所有正则表达式都不匹配。
您可以将它们分成大约20个组合。
(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)
undefined
/None
/null
/...。如果您正在使用真正的正则表达式(对应于形式语言理论中的正则语言,而不是某些类似于Perl的非正则内容),那么您很幸运,因为正则语言在并集下是封闭的。 在大多数正则表达式语言中,管道(|)表示并集。 因此,您应该能够按照以下方式构建一个字符串(表示所需的正则表达式):
(r1)|(r2)|(r3)|...|(r10000)
括号用于分组而不是匹配。任何与此正则表达式匹配的内容都至少匹配一个原始正则表达式。