Python - 为什么正则表达式比在列表中搜索更有效？

Question

当我查看 Google Code Jam Qualification Round 2009 问题时:Alien Language ，简单的想法是从模式中生成所有可能的字符串，并将其保存在列表中，然后测试和计算匹配的字符串。该算法简单明了，但它会消耗非常大的 RAM，您的笔记本电脑无疑会报废。

解决此问题的另一种方法是将 "()" 替换为 "[]" 以使用正则表达式。 Python 嵌入式 re.match() 和 string.replace() 用了不到几秒钟就通过了大型测试。现在的问题是，为什么正则表达式更强大？？

在我的理解中，可能存在某种机制，例如 yield 函数，使您能够生成“生成器”- 可迭代且一次通过。但这是我的猜测。

Answer 1

您的直觉基本上是正确的。

关于计算机科学的细节，你可以查看“nondeterministic finite automaton”和“deterministic finite automaton”的思想。

您可以将正则表达式编译器视为接受正则表达式并生成函数的东西，该函数对您的输入字符串进行操作并保持状态，它会根据规则在使用输入字符串时更新状态源自正则表达式。

如果我从概念上说正则表达式 (ab|cd) 会产生如下行为的东西，希望我不会把事情搞得太多:

def match_ab_or_cd(s):
    state = "start"
    for c in s:
        if state == "start":
            if c == "a":
                state = "state_a"
            elif c == "c":
                state = "state_c"
        elif state == "state_a":
            if c == "b":
                return True
            elif c == "a":
                state = "state_a"
            else:
                state = "start"
        elif state == "state_c":
            if c == "d":
                return True
            elif c == "c":
                state = "state_c"
            else:
                state = "start"
    return False


>>> match_ab_or_cd("ab")
True
>>> match_ab_or_cd("cd")
True
>>> match_ab_or_cd("ae")
False
>>> match_ab_or_cd("aaaaab")
True

因此，对于许多简单的正则表达式，可以生成一台只需要对输入字符串中的每个字符进行一次处理的机器。请记住，虽然有些正则表达式不能很好地发挥作用，例如 (x+x+)+y .

哦，这里是 a fun tool that visualises how regular expressions turn into state machines .你可以把它产生的第一张图片看作是一个中间步骤，第二张图片是可以像上面那样翻译成机器的东西。