我正在寻找能够在字符串中找到最重复序列的算法(可能在Python中实现)。对于REPETITIVE,我指的是在不中断的情况下反复重复的任何字符组合(串联重复)。
我正在寻找的算法与“找到最常见的单词”不同。实际上,重复块不需要是字符串中最常见的单词(substring)。
例如:
s = 'asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs'
> f(s)
'UBAUBAUBAUBAUBA' #the "most common word" algo would return 'BA'
不幸的是,我不知道如何解决这个问题。非常欢迎任何帮助。
UPDATE
一个额外的例子来澄清我希望返回具有最多重复次数的序列,无论其基本构建块是什么。
g = 'some noisy spacer'
s = g + 'AB'*5 + g + '_ABCDEF'*2 + g + 'AB'*3
> f(s)
'ABABABABAB' #the one with the most repetitions, not the max len
@rici的例子:
s = 'aaabcabc'
> f(s)
'abcabc'
s = 'ababcababc'
> f(s)
'ababcababc' #'abab' would also be a solution here
# since it is repeated 2 times in a row as 'ababcababc'.
# The proper algorithm would return both solutions.
以下是基于((\w+?)\2+)
正则表达式的解决方案,但有其他改进:
import re
from itertools import chain
def repetitive(sequence, rep_min_len=1):
"""Find the most repetitive sequence in a string.
:param str sequence: string for search
:param int rep_min_len: minimal length of repetitive substring
:return the most repetitive substring or None
"""
greedy, non_greedy = re.compile(r'((\w+)\2+)'), re.compile(r'((\w+?)\2+)')
all_rep_seach = lambda regex: \
(regex.search(sequence[shift:]) for shift in range(len(sequence)))
searched = list(
res.groups()
for res in chain(all_rep_seach(greedy), all_rep_seach(non_greedy))
if res)
if not sequence:
return None
cmp_key = lambda res: res[0].count(res[1]) if len(res[1]) >= rep_min_len else 0
return max(searched, key=cmp_key)[0]
您可以像这样测试它:
def check(seq, expected, rep_min_len=1):
result = repetitive(seq, rep_min_len)
print('%s => %s' % (seq, result))
assert result == expected, expected
check('asdfewfUBAUBAUBAUBAUBAasdkBAjnfBAenBAcs', 'UBAUBAUBAUBAUBA')
check('some noisy spacerABABABABABsome noisy spacer_ABCDEF_ABCDEFsome noisy spacerABABAB', 'ABABABABAB')
check('aaabcabc', 'aaa')
check('aaabcabc', 'abcabc', rep_min_len=2)
check('ababcababc', 'ababcababc')
check('ababcababcababc', 'ababcababcababc')
主要特点:
((\w+)\2+)
和非贪婪的((\w+)\2+?)
正则表达式;结合使用qazxsw poi(使用特定的正则表达式模式)和qazxsw poi函数:
re.findall()
输出:
max()
关键模式:
import re
# extended sample string
s = 'asdfewfUBAUBAUBAUBAUBAasdkjnfencsADADADAD sometext'
def find_longest_rep(s):
result = max(re.findall(r'((\w+?)\2+)', s), key=lambda t: len(t[0]))
return result[0]
print(find_longest_rep(s))
:
UBAUBAUBAUBAUBA
- 最外面捕获的组,是第一个被捕获的组
((\w+?)\2+)
- 包含在第二个捕获组中的任何非空白字符序列; (....)
- 量词,在一次和无限次之间匹配,尽可能少,根据需要扩展
(\w+?)
- 匹配与第二个捕获组最近匹配的相同文本您正在搜索的是一种在字符串中查找“最大”原始串联重复的算法。这是一篇描述线性时间算法的论文,用于查找字符串中的所有串联重复,并通过扩展所有原始串联重复。 +?
这是我写的一个强力算法。也许它会有用:
\2+