寻找两个字符串之间的最短匹配

Question

我有一个大的日志文件，我想提取两个字符串之间的多行字符串：start和end。

以下是来自inputfile的示例：

start spam
start rubbish
start wait for it...
    profit!
here end
start garbage
start second match
win. end

期望的解决方案应该打印出：

start wait for it...
    profit!
here end
start second match
win. end

我尝试了一个简单的正则表达式，但它返回了从“start spam”开始的所有内容。应该如何处理？

编辑：有关实际计算复杂度的其他信息：

- 实际文件大小：2GB - “start”的出现次数：约12M个，均匀分布 - “end”的出现次数：约800个，靠近文件末尾。

- Eero Aaltonen

---

如果你想匹配start和end之间的内容，那么得到start spam作为开始结果是很正常的... 你能否澄清你想要的行为？ - lcoderre

Answer 1

这个正则表达式应该可以匹配你想要的内容：

(start((?!start).)*?end)

使用re.findall方法和单行模式修饰符re.S在多行字符串中获取所有出现的内容:

使用re.findall方法和单行模式修饰符re.S在多行字符串中获取所有出现的内容:

re.findall('(start((?!start).)*?end)', text, re.S)

在这里查看测试。

- famousgarkin

---

为什么我以前从未听说过regex101呢...？ - RevanProdigalKnight

同样可以在 JS 中工作。 - semanser

你能解释一下 ((?!start).) 吗？ - roschach

@FrancescoBoi 请查看Tempered Greedy Token - 在负向先行断言之前放置点有何不同。 - Wiktor Stribiżew

如果您在使用此模式时遇到性能问题，请使用 re.findall(r'(start([^se]*(?:s(?!tart)[^se]*|e(?!nd)[^se]*)*end)', text)。 - Wiktor Stribiżew

Answer 2

用代码实现 - 基本状态机：

open = False
tmp = []
for ln in fi:
    if 'start' in ln:
        if open:
            tmp = []
        else:
            open = True

    if open:
        tmp.append(ln)

    if 'end' in ln:
        open = False
        for x in tmp:
            print x
        tmp = []

- gkusner

---

完全有效的。 - Eero Aaltonen

Answer 3

这很棘手，因为默认情况下，re 模块不会查找重叠匹配。Python 的新版本有一个新的 regex 模块，允许进行重叠匹配。

https://pypi.python.org/pypi/regex

你需要使用类似于这样的东西

regex.findall(pattern, string, overlapped=True)

如果你被困在 Python 2.x 或其他没有 regex 的环境中，仍然可以通过一些技巧实现。有一个聪明的人在这里解决了这个问题：

Python regex find all overlapping matches?

一旦你拥有了所有可能的重叠（非贪婪模式，我想）匹配，只需确定哪一个是最短的，这应该很容易。

- TheSoundDefense

---

我添加了有关日志文件实际大小的一些信息。在这种情况下，存储所有重叠的匹配项将超出我的计算机磁盘空间的限制。 - Eero Aaltonen

好的，我提供的解决方案返回一个迭代器，所以你实际上不需要存储所有重叠的匹配结果，只需要一两个即可。但考虑到你要解析的文件格式，接受的解决方案可能更适合你的目的。 - TheSoundDefense

Answer 4

你可以用(?s)start.*?(?=end|start)(?:end)?，然后过滤掉不以"end"结尾的所有内容。

- David Ehrmann