NFA与DFA

时间:2022-02-01 01:31:07

正则表达式匹配,包含两个东西,一个是表达式,一个文本。

NFA(Nondeterministic Finite Automaton),不确定有穷自动机,表达式主导,NFA去吃文本,贪婪算法吃下去,如果因为前面吃得太多,导致后面没的吃(后面匹配失败),前面吃的要吐出一点,后面还匹配不成功,前面再吐出一点。。。

DFA(Deterministic Finite Automaton),确定有穷自动机,文本主导,DFA去找吃货,去掉不能吃的吃货,找到最合适的吃货。

举例来说:.*[0-9]+, 去匹配 hangzhou 2015,从程序的角度来看,[0-9]+ 是死代码,因为.*是大范围,[0-9]+是小范围,按道理永远不会被匹配到。

实际的匹配流程是:

.*一直吃到5,然后发现坏了,吃太多了,导致[0-9]+没法匹配,于是吐出5,这样就导致[0-9]+匹配成功,也就是说,.*匹配hangzhou 201,[0-9]+匹配5,显然,这不是好的匹配结果,好的匹配结果应该是,.*匹配hangzhou ,[0-9]+匹配2015,但是NFA不管,我只要匹配成功就好了,才不管你是不是最优匹配呢。

如何解决上面的问题呢?

因为量词是优先匹配的,也就是尽量多吃,解决办法是忽略优先量词,也就是尽量少吃,使用 (.*?)([09]+),匹配结果就是 .*?匹配hangzhou ,[0-9]+匹配2015,

考虑下面的问题,notepad搜索关键字,如果一行多次出现,搜索结果就会重复列出对应的行,如何解决?

使用正则表达式 如下:^(.*abc.*)+$, 仔细思考,可以去掉+,使用^(.*abc.*)$, 前面的.*尽量多吃,abc 匹配最后一行中的最后一个abc,由于notepad 本来就是按行,列出结果的,可以直接写成 .*abc