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

Question

我不确定regex是最好的方法，但它似乎相当适合。实际上，我目前正在使用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

更新:为了让它通过抽运引理，我必须明确地断言所有的重复项都是相邻的。这在之前是隐含的，但我现在明确说明，以确保解决方案是可能的。

Answer 1

regexp不是执行该任务的合适工具。它们基于上下文无关语言的理论，如果字符串包含重复项并删除重复项，它们将无法匹配。你可能会发现关于这个主题的自动机和正则表达式的课程很有趣。

我认为Josay的建议可以是高效和聪明的，但我认为我得到了一个更简单和python的解决方案，尽管它有其局限性。您可以将字符串拆分为行列表，并通过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
>>>

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

• 要解决第一个问题，您可能必须对原始字符串进行第二次迭代以将该集合按顺序放回，或者简单地使用有序集合。
• 如果你有任何符号分隔每张幻灯片，它将帮助你只合并重复的，解决该解决方案的第二个问题。

否则需要一个更复杂的算法，所以你可以考虑接近性和上下文。对于这一点，后缀树可能是一个好主意，有一些python库可以解决这个问题(参考SO的答案)。

编辑:

使用你的算法，我可以使它工作，通过添加支持多行和添加空格和结束行到你的文本匹配:

>>> re.match(r"([w n]+)n1", string, re.MULTILINE).groups()
('I would like thisntext to bennreduced',)

但是，1符号在匹配部分不是正则正则表达式语法，而是一个扩展。但现在已经很晚了，我可能完全错了。也许我应该重读那些课程吗?: -)

我猜regexp引擎的下推自动机能够推匹配，因为它只是一个很长的多行字符串，它可以弹出来匹配。虽然我希望它有副作用…