正则表达式中的子字符串应该根据长度排序的建议背后的原因是什么？

Question

最长优先

>>> p = re.compile('supermanutd|supermanu|superman|superm|super')

最短优先

>>> p = re.compile('super|superm|superman|supermanu|supermanutd')

为什么首选最长的first regex？你知道吗

Answer 1

正则表达式中的替代项是按照您提供的顺序进行测试的，所以如果第一个分支匹配，那么Rx不会检查其他分支。如果您只需要测试匹配性，这并不重要，但是如果您希望基于匹配提取文本，那么这很重要。你知道吗

当短字符串是长字符串的子字符串时，只需要按长度排序。例如，当您有文本时：

supermanutd
supermanu
superman
superm

然后你的第一个Rx你会得到：

>>> regex.findall(string)
[u'supermanutd', u'supermanu', u'superman', u'superm']

但对于第二个Rx：

>>> regex.findall(string)
[u'super', u'super', u'super', u'super', u'super']

用http://www.pythonregex.com/测试正则表达式

Answer 2

我猜这是因为它们是按顺序匹配的，而且匹配较短的子串更快。作为一个极端的例子，一个匹配一个字母|一个巨大的字符串将表现得更好，如果单一的字母（这可能是负责大多数匹配无论如何）测试第一。你知道吗

但实际上你应该测量，而不是猜测。如果您需要一个performant regexp，请根据代表性的测试数据测试变体。你知道吗

Answer 3

正如@MBO所说，备选方案是按照编写顺序进行测试的，一旦其中一个匹配，重新生成的引擎将继续进行后续操作。
这种行为在类似Perl的RE引擎中很常见，最终可以追溯到1985年Bell实验室为第8版Unix设计的RE库。
注意，posix2（从1991年开始）有另一个定义，坚持对整个RE进行最左边最长的匹配，并遵循这个定义，依次对每个子表达式（按词汇顺序）。在posix2中，备选方案的顺序并不重要。你知道吗

然而，行为上的差异通常是：不相关的（如果你只是在测试），被回溯掩盖的（如果较短的匹配导致其余的re失败），或者被其余的re匹配较长的匹配“应该有的”部分补偿的——所以大多数人都没有意识到。你知道吗