优化正则表达式技术

Question

我想知道regex的优化技术

所以我试图从一个40万行的语料库中解析每一个money实例。我还需要包括诸如"$10,999.04"和"one billion and six hundred twenty five thousand 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))*

更重要的是，为了要求它是money的一个实例并避免匹配行，比如"five hundred people were at the event"，我有4个OR'd选项，要求"$", "dollars?", or "cents?"在句子中的特定位置至少出现一次。你知道吗

正则表达式几乎有20k个字符！：（

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

Answer 1

我将把数字和写出的正则表达式分开，分两步进行，首先提取数字量（这是最简单的部分），然后进行写出量。你知道吗

写出来的部分最有问题的地方是，如果你有one hundred people，它会尝试所有的数十亿和数千以及已经在one这个词上的所有东西，只是为了最终发现没有dollars。但更糟糕的是，它会为单词hundred和people重试所有操作…
理想情况下，它会从后面开始，这样它就不会试图把每一个单词都匹配起来，而只匹配‘美元’、‘美分’之类的词，然后才匹配昂贵的部分。你知道吗

因此，如果可能的话，试着把你的文件和写出来的东西前后匹配起来。这肯定会让你的头很难缠，但我敢打赌它会快得多。
如果不可能，我希望现在你至少知道主要的瓶颈在哪里。你知道吗

啊，一些单词边界也可能有助于将匹配从每个字符的减少到每个单词开头的。。。上面我没有提到，但实际上在这个例子中，引擎在'o'处开始匹配，然后在'n'、'e'、'等处再次匹配。你知道吗

Answer 2

我会尝试做这样的事情：

keywords = ["$","dollar","dollars","cent","cents"]
my_file = r"c:\file.txt"
output = r"c:\output.txt"
filtered_lines = []
with open(my_file,"r") as f:
     for line in f:
         for k in keywords:
             if k in line:
                filtered_lines.append(line)
                break
with open(output,"w") as o:
    o.write("\n".join(filtered_lines))

Answer 3

你问的是如何优化性能，所以让我们关注一下。regexp引擎真正慢的原因是backtracking，而导致回溯的原因是可能在字符串的不同位置成功的部分，没有明确的方法来决定。所以试试这些经验法则：

1. 在上面的回溯链接中：“嵌套重复运算符时，请绝对确保只有一种方法匹配相同的匹配。”

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

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

4. 确保regexp中未受约束的部分在长度上是有界的，特别是如果后面的部分不能被可靠地识别的话。像A.*B?这样的事情是自找麻烦的，它可以匹配以A开头的任何东西。

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

一般来说，保持简单。我不知道你是如何做到这项任务的20K字符，但我敢打赌有一些方法可以简化它。一个考虑因素是，它可以匹配的东西，你不会看到无论如何。你知道吗

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

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

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

1. 如果任务（或分配）允许您分步进行搜索，请这样做。 做任何事情的regexp都必须非常复杂，以至于它比简单地按顺序运行几个搜索要慢。

2. 即使您被限制使用一个monster regexp，也要将它编写成多个片段，并使用python将其组装成一个字符串。它在执行时不会有任何区别，但是使用起来会容易得多。