python - 删除长度超过 x 个字符的字符串的所有副本(正则表达式？)

Question

我不确定正则表达式是否是最好的方法，但它似乎相当适合。本质上，我目前正在使用 pdfminer 解析一些 pdf，缺点是这些 pdf 是导出的 powerpoint 幻灯片，这意味着所有动画都显示为相当长的字符串副本。理想情况下，我只需要每个字符串的一个副本，而不是动画每个阶段的副本。现在我正在使用的当前正则表达式模式是这样的:

re.sub(r"([\w^\w]{10,})\1{1,}", "\1", string)

虽然出于某种原因，这似乎并没有改变输入字符串。我觉得由于某种原因 python 无法识别捕获组，但我不确定如何解决该问题。任何想法表示赞赏。

例子:

I would like this
text to be

reduced
I would like this
text to be

reduced

输出:

I would like this
text to be

reduced

更新:为了让它通过 pumping lemma我必须特别断言所有重复项都是相邻的。这是之前暗示的，但我现在明确表示以确保解决方案是可能的。

Answer 1

正则表达式不是完成该任务的正确工具。它们基于 context free languages 的理论, 如果字符串包含重复项并删除重复项，它们将无法匹配。您可以在 automata 上找到类(class)和 regexps阅读该主题很有趣。

我认为 Josay 的建议既高效又聪明，但我认为我得到了一个更简单的 pythonic 解决方案，尽管它有其局限性。您可以将字符串拆分为行列表，然后通过 set() 传递它:

>>> s = """I would like this
... text to be
... 
... reduced
... I would like this
... text to be
... 
... reduced"""
>>> print "\n".join(set(s.splitlines()))
I would like this

text to be
reduced
>>>

该解决方案的唯一问题是您将丢失行的原始顺序(该示例是一个很好的反例)。此外，如果您在两个不同的上下文中使用同一行，您最终将只有一行。

• 要解决第一个问题，您可能必须再次遍历原始字符串以使该集合恢复原状，或者简单地使用 ordered set。 .
• 如果你有任何符号来分隔每张幻灯片，它会帮助你只合并重复项，解决该解决方案的第二个问题。

否则将需要更复杂的算法，以便您可以考虑邻近性和上下文。为此，后缀树可能是个好主意，并且有 python 库(cf that SO answer)。

编辑:

使用您的算法，我可以通过添加对多行的支持并为您的文本匹配添加空格和结尾来使其工作:

>>> re.match(r"([\w \n]+)\n\1", string, re.MULTILINE).groups()
('I would like this\ntext to be\n\nreduced',)

不过，\1 表示法在匹配部分并不是正则表达式语法，而是一种扩展。但是这里已经很晚了，我也可能完全错了。也许我应该重读那些类(class)？ :-)

我猜想正则表达式引擎的下推自动机能够推送匹配项，因为它只是一个长的多行字符串，它可以弹出来匹配。虽然我预计它会有副作用......