问题正则表达式删除字符串中重复的字符模式

我有一个可能有重复字符模式的字符串，例如

'xyzzyxxyzzyxxyzzyx'

我需要编写一个正则表达式，用它最小的重复模式替换这样的字符串：

'xyzzyxxyzzyxxyzzyx' becomes 'xyzzyx',

'abcbaccbaabcbaccbaabcbaccba' becomes 'abcbaccba'

12235

2017-09-17 23:48

起源

模式是已知的，还是在寻找字符串中的任何重复模式？ - Joel

我正在寻找最小的重复模式。 - arshajii

答案:

使用以下内容：

> re.sub(r'(.+?)\1+', r'\1', 'xyzzyxxyzzyxxyzzyx')
'xyzzyx'
> re.sub(r'(.+?)\1+', r'\1', 'abcbaccbaabcbaccbaabcbaccba')
'abcbaccba'
> re.sub(r'(.+?)\1+', r'\1', 'iiiiiiiiiiiiiiiiii')
'i'

它基本上匹配重复自己的模式 (.+?)\1+，并删除除第一组中捕获的重复模式之外的所有内容 \1。另请注意，在此使用不情愿的限定符，即 +? 将使正则表达式回溯相当多。

DEMO。

2017-09-17 23:54

这个问题是它在这种情况下失败了：>>> re.sub（r'（\ w +）\ 1 +'，r'\ 1'，'iiiiiiiiiiiiiiiiii'）产生'iiiiiiiii'而不是'i' - mercador

@mercador：我明白了 + 量词不愿意而不是贪心。我已经更新了我的答案。 - João Silva

由于您需要最小的重复模式，因此以下内容适用于您：

re.sub(r'^(.+?)\1+$', r'\1', input_string)

该 ^ 和 $ 锚点确保你不会在字符串的中间获得匹配，并使用 .+? 而不仅仅是 .+ 您将获得最短的模式（使用类似字符串比较结果 'aaaaaaaaaa'）。

2017-09-18 00:05

请记住，如果这可能需要很长时间才能失败 input_string 是这样的 "a" * 1000000 + "b"。 - hobbs

没有回溯的正则表达式的任何想法？该 .+? 将导致沉重的回溯。 - Kash

如果您阅读“Programming Perl”这样的书，您可以通过“重”示例找到正则表达式的实现。我认为，这对正则表达式来说不是一项快速的任务。 - gaussblurinc

做了一些定时测试，这个正则表达式是O（n），其中n是字符串的长度，所以这里的回溯不是问题。灾难性的回溯嵌套重复是一个更大的问题，你可以像O（2 ^ n）那样获得指数式增长。实际上可能没有一种使用普通字符串操作的更有效的方法（不确定这一点）。 - Andrew Clark

试试这个正则表达式模式并捕获第一组：

^(.+?)\1+$

^ 用于开始字符串/行的锚点
. 除换行符之外的任何字符
+ 量词表示至少1次出现
? 做的 + 懒惰而不是贪婪，因此给你最短的模式
() 捕获组
\1+ 用量词反向引用表示该模式应该至少重复一次
$ 用于字符串/行结尾的锚点

在这里测试一下： Rubular

上述解决方案会影响性能的很多回溯。如果你知道这些字符串中不允许哪些字符，那么你可以使用一个否定的characted集来消除回溯。例如，如果不允许空格，那么

^([^\s]+)\1+$

2017-09-18 03:13

问题 正则表达式删除字符串中重复的字符模式

答案:

热门问题

问题正则表达式删除字符串中重复的字符模式