python - 优化正则表达式技术

Question

我想知道正则表达式的优化技术

所以我试图从 400k 行的语料库中解析每一个 money 实例。我还需要包含诸如 "$10,999.04" 和 "1625,000 dollars" 之类的行以及介于两者之间的所有内容。这需要一个非常冗长的正则表达式，其中包含多个组实例，例如

MONEYEXPRESSION = '(?:\d\d?\d?(?:,?\d{3})*(?:\.\d+)?)'
(one|two|...|ninety[\s-]?nine|hundred|a hundred|MONEYEXPRESSION)((\s*and\s*|\s*-\s*|\s*)(one|two|...|ninety[\s-]?nine|hundred|a hundred|MONEYEXPRESSION))*

更重要的是，为了要求它是金钱的一个实例并避免匹配诸如 "five hundred people were at the event" 之类的行，我有 4 个 OR'd 选项需要“$”、“dollars?”或“cents?” 在句子的特定位置至少出现一次。

正则表达式将近 20k 个字符! :(

你可以想象，用这么广泛的表达方式，加上任何不好的做法，真的会增加时间。我在语料库上运行了2个小时，仍然没有匹配完成。我想知道优化和修剪不必要的正则表达式的一些最佳实践是什么。我正在使用的操作是昂贵的，可以补充更好的操作。是否有更好的方法来解决这个问题？

Answer 1

您问的是优化性能，所以让我们专注于此。真正让正则表达式引擎变慢的是 backtracking ，而导致回溯的是那些可能在字符串中的不同位置成功的部分，没有明确的方法来决定。所以试试这些经验法则:

1. 来自上面的回溯链接:“嵌套重复运算符时，绝对确保只有一种方法可以匹配相同的匹配项。”

2. 避免使用大型可选组件。而不是像 (<number>? <number>)? <number> 这样的东西要匹配包含空格分隔元素的序列，请编写 (<number> ?)+ .

3. 避免空字符串可以满足的组件——引擎将尝试在每个位置满足它们。

4. 确保正则表达式中不受约束的部分在长度上有限制，尤其是在后面的部分无法可靠识别的情况下。像 A.*B? 这样的东西自找麻烦 -- 这可以匹配以 A 开头的任何 .

5. 不要使用前瞻/后视。几乎总是有更简单的方法。

更一般地说，保持简单。我不确定您是如何设法完成此任务的 20K 个字符，但我敢打赌有一些方法可以简化它。一个考虑是可以匹配您无论如何都不会看到的东西。

例如，为什么要匹配从 1 到 99 的所有数字，而不仅仅是它们的组成部分？是的，您会匹配诸如“九九十加元”之类的废话，但这没有坏处。 您正在搜索金额，而不是验证输入。例如，这应该匹配所有小于一百万美元的书面金额:

((one|two|three|...|twenty|thirty|...|ninety|hundred|thousand|and) ?)+ (dollars?|euros?)\b

由于这被标记为“python”，这里还有两个建议:

1. 如果任务(或分配)允许您将搜索分解为多个步骤，那么就这样做。做所有事情的正则表达式通常必须非常复杂，以至于它比简单地按顺序运行多个搜索要慢。

2. 即使您被迫使用一个怪物正则表达式，也可以将其分段编写并使用 python 将其组装成一个字符串。它在执行时不会有任何区别，但使用起来会容易得多。