我正在寻找一种方法来测试一个给定的字符串是否在整个字符串中重复自己。
例子:
[
'0045662100456621004566210045662100456621', # '00456621'
'0072992700729927007299270072992700729927', # '00729927'
'001443001443001443001443001443001443001443', # '001443'
'037037037037037037037037037037037037037037037', # '037'
'047619047619047619047619047619047619047619', # '047619'
'002457002457002457002457002457002457002457', # '002457'
'001221001221001221001221001221001221001221', # '001221'
'001230012300123001230012300123001230012300123', # '00123'
'0013947001394700139470013947001394700139470013947', # '0013947'
'001001001001001001001001001001001001001001001001001', # '001'
'001406469760900140646976090014064697609', # '0014064697609'
]
是重复自己的字符串,和
[
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
是一些不这样做的例子。
我给出的字符串的重复部分可能相当长,字符串本身可能有500个或更多字符,因此循环每个字符试图构建一个模式,然后检查模式与字符串的其余部分似乎非常慢。再乘以几百个字符串,我看不出任何直观的解决方案。
我研究了一下正则表达式,当你知道你在寻找什么,或者至少知道你在寻找的模式的长度时,它们似乎很有用。不幸的是,我两个都不知道。
我怎么知道一个字符串是否在重复它自己,如果是的话,最短的重复子序列是什么?
Non-regex解决方案:
def repeat(string):
for i in range(1, len(string)//2+1):
if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
return string[0:i]
更快的非正则表达式解决方案,感谢@ThatWeirdo(见评论):
def repeat(string):
l = len(string)
for i in range(1, len(string)//2+1):
if l%i: continue
s = string[0:i]
if s*(l//i) == string:
return s
上面的解决方案很少会比原来的方案慢几个百分点,但通常会快一点——有时会快很多。对于较长的字符串,它仍然没有davidism的更快,对于较短的字符串,zero的regex解决方案更好。它的输出速度最快(根据davidism在github上的测试-见他的答案),字符串大约为1000-1500个字符。无论如何,在我测试的所有情况下,它都是可靠的第二快(或更好)。谢谢,ThatWeirdo。
测试:
print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))
结果:
009
2547
abcde
None
None
None
这里有一个使用正则表达式的解决方案。
import re
REPEATER = re.compile(r"(.+?)\1+$")
def repeated(s):
match = REPEATER.match(s)
return match.group(1) if match else None
遍历问题中的例子:
examples = [
'0045662100456621004566210045662100456621',
'0072992700729927007299270072992700729927',
'001443001443001443001443001443001443001443',
'037037037037037037037037037037037037037037037',
'047619047619047619047619047619047619047619',
'002457002457002457002457002457002457002457',
'001221001221001221001221001221001221001221',
'001230012300123001230012300123001230012300123',
'0013947001394700139470013947001394700139470013947',
'001001001001001001001001001001001001001001001001001',
'001406469760900140646976090014064697609',
'004608294930875576036866359447',
'00469483568075117370892018779342723',
'004739336492890995260663507109',
'001508295625942684766214177978883861236802413273',
'007518796992481203',
'0071942446043165467625899280575539568345323741',
'0434782608695652173913',
'0344827586206896551724137931',
'002481389578163771712158808933',
'002932551319648093841642228739',
'0035587188612099644128113879',
'003484320557491289198606271777',
'00115074798619102416570771',
]
for e in examples:
sub = repeated(e)
if sub:
print("%r: %r" % (e, sub))
else:
print("%r does not repeat." % e)
... 产生如下输出:
'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.
正则表达式(.+?)\1+$分为三部分:
(.+?)是一个匹配组,包含至少一个(但尽可能少)任意字符(因为+?是贪婪的,)。
\1+检查第一部分中匹配组是否至少重复一次。
$检查字符串的结尾,以确保在重复的子字符串之后没有额外的非重复内容(并且使用re.match()确保在重复的子字符串之前没有非重复文本)。
在Python 3.4及以后版本中,你可以放弃$而使用re.fullmatch(),或者(至少在任何Python 2.3版本中)使用re.search()和正则表达式^(.+?)\1+$,所有这些都取决于个人的喜好。
下面是这个问题的不同答案的一些基准。有一些令人惊讶的结果,包括完全不同的性能取决于测试的字符串。
一些函数被修改以适应Python 3(主要是用//替换/以确保整数除法)。如果你看到错误,想要添加你的函数,或者想要添加另一个测试字符串,在Python聊天室ping @ZeroPiraeus。
总之:对于OP在这里(通过这条评论)提供的大量示例数据,最佳和最差的解决方案之间大约有50倍的差异。David Zhang的解决方案显然是赢家,在大型示例集中,它的性能比其他所有解决方案高出约5倍。
在非常大的“不匹配”情况下,有两个答案非常慢。否则,根据测试的不同,这些功能似乎是相同的或明显的赢家。
以下是结果,包括使用matplotlib和seaborn绘制的图,以显示不同的分布:
语料库1(提供的示例-小集)
mean performance:
0.0003 david_zhang
0.0009 zero
0.0013 antti
0.0013 tigerhawk_2
0.0015 carpetpython
0.0029 tigerhawk_1
0.0031 davidism
0.0035 saksham
0.0046 shashank
0.0052 riad
0.0056 piotr
median performance:
0.0003 david_zhang
0.0008 zero
0.0013 antti
0.0013 tigerhawk_2
0.0014 carpetpython
0.0027 tigerhawk_1
0.0031 davidism
0.0038 saksham
0.0044 shashank
0.0054 riad
0.0058 piotr
语料库2(提供的示例-大集)
mean performance:
0.0006 david_zhang
0.0036 tigerhawk_2
0.0036 antti
0.0037 zero
0.0039 carpetpython
0.0052 shashank
0.0056 piotr
0.0066 davidism
0.0120 tigerhawk_1
0.0177 riad
0.0283 saksham
median performance:
0.0004 david_zhang
0.0018 zero
0.0022 tigerhawk_2
0.0022 antti
0.0024 carpetpython
0.0043 davidism
0.0049 shashank
0.0055 piotr
0.0061 tigerhawk_1
0.0077 riad
0.0109 saksham
语料库3(边缘情况)
mean performance:
0.0123 shashank
0.0375 david_zhang
0.0376 piotr
0.0394 carpetpython
0.0479 antti
0.0488 tigerhawk_2
0.2269 tigerhawk_1
0.2336 davidism
0.7239 saksham
3.6265 zero
6.0111 riad
median performance:
0.0107 tigerhawk_2
0.0108 antti
0.0109 carpetpython
0.0135 david_zhang
0.0137 tigerhawk_1
0.0150 shashank
0.0229 saksham
0.0255 piotr
0.0721 davidism
0.1080 zero
1.8539 riad
测试和原始结果可以在这里找到。