3

我有多个文件，每个文件都在搜索一系列单词。

我的正则表达式基本上搜索 word1 后跟 word2 后跟 word 3 等的序列。所以表达式看起来像：

strings = re.findall('word1.*?word2.*?word3', f.read(), re.DOTALL)

对于 20kb 以下的文件，表达式执行得很好。但是，对于大于 20 kb 的文件，执行时间会成倍增加，并且对于接近 100 kb 的文件，进程会完全挂起。看来（在阅读了以前的线程之后）问题与使用 .* 和 re.DOTALL 相关 - 导致“灾难性回溯”。推荐的解决方案是逐行提供输入文件，而不是将整个文件读入单个内存缓冲区。

但是，我的输入文件充满了随机空格和“\n”换行符。我的单词序列也很长，并且出现在多行中。因此，我需要将整个文件连同 re.DOTALL 一起输入到正则表达式中 - 否则逐行搜索将永远找不到我的序列。

有什么办法吗？

4

3 回答 3

2

如果您从字面上搜索三个单词的出现，其中根本没有正则表达式模式，则根本不需要使用正则表达式 - 正如我写这个答案时@Bart所建议的那样：)。像这样的东西可能会起作用（未经测试，并且可能更漂亮）：

with open('...') as f:
    contents = f.read()

words = ['word1', 'word2', 'word3']
matches = []
start_idx = 0
try:
    while True:
        cand = []
        for word in words:
            word_idx = contents.index(word, start_idx)
            cand.append(word_idx)
            start_idx = word_idx + len(word)
        matches.append(cand)
except ValueError:  # from index() failing
    pass

这会将索引放入matches; 如果你想要一个与 findall 等效的结果，你可以这样做，说，

found = [contents[match[0]:match[-1]+len(words[-1]] for match in matches]

index您还可以通过将调用替换为文件上的等效函数来使这种方法工作而无需事先读取整个文件。我不认为 stdlib 包含这样的功能；您可能必须在文件对象上手动使用readline()和tell()或类似的方法。

于 2013-04-04T21:24:55.277 回答
1

发生这种情况的原因是因为 python 的正则表达式引擎使用回溯。在每个.*，如果没有找到下面的单词，引擎必须一直走到字符串的末尾（100kb）然后回溯。现在考虑如果在最后一场比赛之后有许多“几乎匹配”会发生什么。引擎从匹配开始到字符串结尾不断地来回跳跃。

您可以使用基于 NFA 而不是回溯的正则表达式引擎来修复它。请注意，这限制了您可以使用的正则表达式的种类（没有回溯或任意零宽度断言），但它适合您的用例。

你可以在这里找到这样的引擎。您可以在www.debuggex.com上可视化 nfa 引擎的工作原理。

于 2013-04-04T21:07:11.950 回答
0

您可以使用循环一次搜索一个单词。我在str.find()这里使用它是因为它对于简单的子字符串搜索更快，但您也可以调整此代码以re.search()代替使用。

def findstrings(text, words):
    end = 0
    while True:
        start = None
        for word in words:
            pos = text.find(word, end) #starts from position end
            if pos < 0:
                return
            if start is None:
                start = pos
            end = pos + len(word)
        yield text[start:end]


#usage in place of re.findall('word1.*?word2.*?word3', f.read(), re.DOTALL)
list(findstrings(f.read(), ['word1', 'word2', 'word3']))
于 2013-04-05T05:46:40.653 回答