使用正则表达式删除字符串中重复的字符模式

Question

使用正则表达式删除字符串中重复的字符模式

11

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

'xyzzyxxyzzyxxyzzyx'

我需要编写一个正则表达式，用于将此字符串替换为其最小重复模式：

'xyzzyxxyzzyxxyzzyx' becomes 'xyzzyx',

'abcbaccbaabcbaccbaabcbaccba' becomes 'abcbaccba'

- mercador

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

1

他在寻找最小的重复模式，我猜。 - arshajii

3个回答

4

如果您需要最小的重复模式，以下内容可能适用于您：

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

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

- Andrew Clark

1

请记住，如果 input_string 类似于 "a" * 1000000 + "b"，那么这可能需要很长时间才能失败。 - hobbs

1

有没有不需要回溯的正则表达式的想法？ .+? 会导致严重的回溯问题。 - Kash

如果你阅读了《Perl编程》这样的书籍，你可以找到具有“重量级”示例的正则表达式实现。我认为，对于正则表达式来说，这不是一个快速的任务。 - gaussblurinc

1

进行了一些计时测试，发现这个正则表达式的时间复杂度是O(n)，其中n是字符串的长度，因此回溯在这里不是一个问题。灾难性回溯是嵌套重复中更大的问题，其中您可能会获得指数增长，如O(2^n)。实际上，使用普通字符串操作可能没有更有效的方法（对此不确定）。 - Andrew Clark

2

尝试使用这个正则表达式模式，并捕获第一个分组:

^(.+?)\1+$

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

在此进行测试：Rubular

上述解决方案进行了大量回溯，影响了性能。如果您知道这些字符串中不允许出现哪些字符，则可以使用否定字符集来消除回溯。例如，如果不允许出现空格，则可以使用以下正则表达式：

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

- Kash

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- João Silva · Accepted Answer

请使用以下内容：

> 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。