在字符串中查找重复的字符组合

Question

我有一个字符串,它包含一个很长的句子,没有空格/空格.

mystring = "abcdthisisatextwithsampletextforasampleabcd"

我想找到包含最少4个字符的所有重复子字符串.

所以我想实现这样的目标:

'text' 2 times
'sample' 2 times
'abcd' 2 times

作为两者abcd,text并且sample可以在mystring它们中找到两次,它们被认为是具有超过4个字符长度的恰当匹配的子串.重要的是我要寻找重复的子串,找到只有现有的英语单词不是必需的.

我找到的答案有助于在空白文本中查找重复项,但是当字符串中没有空格和空格时,我找不到适当的资源来覆盖这种情况.如果有人能告诉我如何以最有效的方式完成这项工作,我将非常感激.

Answer 1

让我们一步一步来看看.您应该注意几个子任务:

1. 识别长度为4或更长的所有子串.
2. 计算这些子串的出现次数.
3. 过滤所有子串,出现2次或更多次.

实际上,您可以将它们全部放入几个语句中.为了便于理解,一次更容易理解它们.

以下示例均使用

mystring = "abcdthisisatextwithsampletextforasampleabcd"
min_length = 4

1.给定长度的子串

您可以通过切片轻松获得子串 - 例如,mystring[4:4+6]为您提供长度为6的位置4的子串:'thisis'.更一般地说,您需要表单的子字符串mystring[start:start+length].

所以,你需要什么价值观start和length？

• start 必须...
  • 覆盖所有子串,因此它必须包括第一个字符:start in range(0, ...).
  • 不映射到短子串,因此它可以max_length在结束前停止字符:start in range(..., len(mystring) - max_length + 1).
• length 必须...
  • 覆盖长度为4的最短子串:length in range(min_length, ...).
  • 之后不超过剩余的字符串i:length in range(..., len(mystring) - i + 1))

这些+1术语来自将长度(> = 1)转换为索引(> = 0).你可以把这一切放在一起理解:

substrings = [
    mystring[i:i+j]
    for i in range(0, len(mystring) - min_length + 1)
    for j in range(min_length, len(mystring) - i + 1)
]

2.计算子串

平凡的是,您希望保留每个子字符串的计数.为每个特定对象保留任何东西是为了做什么dict.所以你应该使用子串作为键并计算为a中的值dict.从本质上讲,这对应于:

counts = {}
for substring in substrings:
    try:  # increase count for existing keys, set for new keys
         counts[substring] += 1
    except KeyError:
         counts[substring] = 1

你可以简单地喂你substrings到collections.Counter,它产生类似上面的东西.

>>> counts = collections.Counter(substrings)
>>> print(counts)
Counter({'abcd': 2, 'abcdt': 1, 'abcdth': 1, 'abcdthi': 1, 'abcdthis': 1, ...})

注意副本如何'abcd'映射到2的计数.

3.过滤重复的子串

所以现在你有了你的子串和每个的计数.您需要删除非重复的子字符串 - 计数为1的子字符串.

Python提供了几种用于过滤的结构,具体取决于您想要的输出.这些工作如果counts是常规的dict:

>>> list(filter(lambda key: counts[key] > 1, counts))
['abcd', 'text', 'samp', 'sampl', 'sample', 'ampl', 'ample', 'mple']
>>> {key: value for key, value in counts.items() if value > 1}
{'abcd': 2, 'ampl': 2, 'ample': 2, 'mple': 2, 'samp': 2, 'sampl': 2, 'sample': 2, 'text': 2}

使用Python原语

Python附带了原语,允许您更有效地执行此操作.

1. 使用生成器来构建子字符串.生成器会动态构建其成员,因此您实际上永远不会将它们全部存储在内存中.对于您的用例,您可以使用生成器表达式:

   substrings = (
       mystring[i:i+j]
       for i in range(0, len(mystring) - min_length + 1)
       for j in range(min_length, len(mystring) - i + 1)
   )
   

2. 使用预先存在的Counter实现.Python附带了一个dict计算其成员的类似容器:collections.Counter可以直接消化你的子串生成器.特别是在较新版本中,这样效率更高.

   counts = collections.Counter(substrings)
   

3. 您可以利用Python的惰性过滤器来检查一个子字符串.的filter内建或另一个发生器发生器表达可以一次产生一个结果,而不存储它们全部在存储器中.

   for substring in filter(lambda key: counts[key] > 1, counts):
       print(substring, 'occurs', counts[substring], 'times')
   

Answer 2

脚本(需要时在评论中解释):

from collections import Counter

mystring = "abcdthisisatextwithsampletextforasampleabcd"
mystring_len = len(mystring)

possible_matches = []
matches = []

# Range `start_index` from 0 to 3 from the left, due to minimum char count of 4
for start_index in range(0, mystring_len-3):
    # Start `end_index` at `start_index+1` and range it throughout the rest of
    # the string
    for end_index in range(start_index+1, mystring_len+1):
        current_string = mystring[start_index:end_index]
        if len(current_string) < 4: continue # Skip this interation, if len < 4
        possible_matches.append(mystring[start_index:end_index])

for possible_match, count in Counter(possible_matches).most_common():
    # Iterate until count is less than or equal to 1 because `Counter`'s
    # `most_common` method lists them in order. Once 1 (or less) is hit, all
    # others are the same or lower.
    if count <= 1: break
    matches.append((possible_match, count))

for match, count in matches:
    print(f'\'{match}\' {count} times')

输出:

'abcd' 2 times
'text' 2 times
'samp' 2 times
'sampl' 2 times
'sample' 2 times
'ampl' 2 times
'ample' 2 times
'mple' 2 times

Answer 3

没人在用re!使用正则表达式内置模块回答[ab]的时间;)

import re

查找重复的所有最大子串

repeated_ones = set(re.findall(r"(.{4,})(?=.*\1)", mystring))

这匹配最长的子串,其后至少有一次重复(没有消耗).因此,它会找到所有不连续的子串,这些子串只会产生最长的字符串.

查找重复的所有子字符串,包括重叠

mystring_overlap = "abcdeabcdzzzzbcde"
# In case we want to match both abcd and bcde
repeated_ones = set()
pos = 0

while True:
    match = re.search(r"(.{4,}).*(\1)+", mystring_overlap[pos:])
    if match:
        repeated_ones.add(match.group(1))
        pos += match.pos + 1
    else:
        break

这确保了所有 -不仅是不相交的 - 具有重复的子串返回.它应该慢得多,但完成工作.

如果你想要除了重复的最长字符串,所有子字符串,那么:

base_repetitions = list(repeated_ones)

for s in base_repetitions:
    for i in range(4, len(s)):
        repeated_ones.add(s[:i])

这将确保对于具有重复的长子串,您还有re.search代码找到的较小的子串--eg"sample"和"ample" ; 而且上面的片段还添加了"samp","sampl","ampl".

计算比赛

因为(按设计)我们计算的子串是非重叠的,所以该count方法是可行的:

from __future__ import print_function
for substr in repeated_ones:
    print("'%s': %d times" % (substr, mystring.count(substr)))

结果

查找最大子串:

问题的原始mystring:

{'abcd', 'text', 'sample'}

与mystring_overlap样品:

{'abcd'}

查找所有子字符串:

问题的原始mystring:

{'abcd', 'ample', 'mple', 'sample', 'text'}

...如果我们添加代码来获取所有子字符串,那么,当然,我们绝对会得到所有子字符串:

{'abcd', 'ampl', 'ample', 'mple', 'samp', 'sampl', 'sample', 'text'}

与mystring_overlap样品:

{'abcd', 'bcde'}

未来的工作

可以使用以下步骤过滤查找所有子字符串的结果:

• 拿一根"A"
• 检查这个匹配是否是另一个匹配的子串,称之为"B"
• 如果有"B"匹配,请检查该匹配"B_n"的计数器
• 如果"A_n = B_n",则删除A.
• 转到第一步

"A_n <B_n"不会发生,因为A小于B(是子串),因此必须至少有相同的重复次数.

如果"A_n> B_n"意味着较小的子字符串存在一些额外的匹配,那么它是一个不同的子字符串,因为它在不重复B的地方重复.