3

我试图在主字符串（所有长度）中找到所有出现的子字符串。我的函数接受一个字符串，然后返回每个子字符串的字典（当然，它不止一次出现）以及它出现的次数（字典的格式：）{substring: # of occurrences, ...}。我正在使用collections.Counter(s)它来帮助我。

这是我的功能：

from collections import Counter

def patternFind(s):
    patterns = {}
    for index in range(1, len(s)+1)[::-1]:
        d = nChunks(s, step=index)
        parts = dict(Counter(d))
        patterns.update({elem: parts[elem] for elem in parts.keys() if parts[elem] > 1})
    return patterns

def nChunks(iterable, start=0, step=1):
    return [iterable[i:i+step] for i in range(start, len(iterable), step)]

我有一个字符串，data大约有 2500 个随机字母（以随机顺序）。但是，其中插入了 2 个字符串（随机点）。假设这个字符串是“TEST”。data.count('TEST')返回 2。但是，patternFind(data)['TEST']给了我一个KeyError. 因此，我的程序没有检测到其中的两个字符串。

我做错了什么？谢谢！

编辑：我创建测试实例的方法：

def createNewTest():
    n = randint(500, 2500)
    x, y = randint(500, n), randint(500, n)
    s = ''
    for i in range(n):
        s += choice(uppercase)
        if i == x or i == y: s += "TEST"
    return s
4

4 回答 4

4

使用正则表达式

除了count()您描述的方法之外，正则表达式是一个明显的选择

import re

needle = r'TEST'

haystack = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklagh'
pattern = re.compile(needle)

print len(re.findall(pattern, haystack))

捷径

如果您需要构建子字符串字典，则可能只使用这些字符串的子集即可。假设您知道needle要在 中查找 ，那么您只需要与 .长度相同data的子字符串字典。这是非常快的。dataneedle

from collections import Counter

needle = "TEST"

def gen_sub(s, len_chunk):
    for start in range(0, len(s)-len_chunk+1):
        yield s[start:start+len_chunk]

data = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklaghTESz'
parts = Counter([sub for sub in gen_sub(data, len(needle))])

print parts[needle]

蛮力：构建所有子字符串的字典

如果您需要计算所有可能的子字符串，这可行，但速度很慢：

from collections import Counter

def gen_sub(s):
    for start in range(0, len(s)):
        for end in range(start+1, len(s)+1):
            yield s[start:end]

data = 'khjkzahklahjTESTkahklaghTESTjklajhkhz'
parts = Counter([sub for sub in gen_sub(data)])

print parts['TEST']

改编自此的子字符串生成器：https ://stackoverflow.com/a/8305463/1290420

于 2013-04-03T14:20:05.490 回答
3

虽然 jurgenreza 已经解释了为什么您的程序不起作用，但解决方案仍然很慢。如果你只检查s你知道s[:-1]重复的子串，你会得到一个更快的解决方案（通常快一百倍甚至更多）：

from collections import defaultdict

def pfind(prefix, sequences):
    collector = defaultdict(list)
    for sequence in sequences:
        collector[sequence[0]].append(sequence)
    for item, matching_sequences in collector.items():
        if len(matching_sequences) >= 2:
            new_prefix = prefix + item
            yield (new_prefix, len(matching_sequences))
            for r in pfind(new_prefix, [sequence[1:] for sequence in matching_sequences]):
                yield r

def find_repeated_substrings(s):
    s0 = s + " "
    return pfind("", [s0[i:] for i in range(len(s))])

如果你想要一个字典，你可以这样称呼它：

result = dict(find_repeated_substrings(s))

在我的机器上，运行 2247 个元素需要 0.02 秒，而原始（更正）解决方案需要 12.72 秒。

（请注意，这是一个相当幼稚的实现；使用索引而不是子字符串应该更快。）

编辑：以下变体适用于其他序列类型（不仅是字符串）。此外，它不需要哨兵元素。

from collections import defaultdict

def pfind(s, length, ends):
    collector = defaultdict(list)
    if ends[-1] >= len(s):
        del ends[-1]
    for end in ends:
        if end < len(s):
            collector[s[end]].append(end)
    for key, matching_ends in collector.items():
        if len(matching_ends) >= 2:
            end = matching_ends[0]
            yield (s[end - length: end + 1], len(matching_ends))
            for r in pfind(s, length + 1, [end + 1 for end in matching_ends if end < len(s)]):
                yield r


def find_repeated_substrings(s):
    return pfind(s, 0, list(range(len(s))))

这仍然存在非常长的子字符串会超过递归深度的问题。您可能想要捕获异常。

于 2013-04-11T11:53:01.843 回答
2

在这里，您可以找到一个使用递归包装器的解决方案，该包装器string.find()搜索主字符串中子字符串的所有出现。该collectallchuncks()函数将defaultdict所有子字符串作为键返回，并为每个子字符串返回在主字符串中找到子字符串的所有索引的列表。

import collections

# Minimum substring size, may be 1
MINSIZE = 3

# Recursive wrapper
def recfind(p, data, pos, acc):
    res = data.find(p, pos)
    if res == -1:
        return acc
    else:
        acc.append(res)
        return recfind(p, data, res+1, acc)

def collectallchuncks(data):
    res = collections.defaultdict(str)
    size = len(data)
    for base in xrange(size):
        for seg in xrange(MINSIZE, size-base+1):
            chunk = data[base:base+seg]
            if data.count(chunk) > 1:
                res[chunk] = recfind(chunk, data, 0, [])
    return res

if __name__ == "__main__":
    data = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklaghTESz'
    allchuncks = collectallchuncks(data)
    print 'TEST', allchuncks['TEST']
    print 'hklag', allchuncks['hklag']

编辑：如果您只需要主字符串中每个子字符串的出现次数，您可以轻松获得它摆脱递归函数：

import collections

MINSIZE = 3

def collectallchuncks2(data):
    res = collections.defaultdict(str)
    size = len(data)
    for base in xrange(size):
        for seg in xrange(MINSIZE, size-base+1):
            chunk = data[base:base+seg]
            cnt = data.count(chunk)
            if cnt > 1:
                res[chunk] = cnt
    return res

if __name__ == "__main__":
    data = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklaghTESz'
    allchuncks = collectallchuncks2(data)
    print 'TEST', allchuncks['TEST']
    print 'hklag', allchuncks['hklag']
于 2013-04-06T00:11:10.610 回答
2

问题出在你的nChunks功能上。它不会为您提供所有必要的块。

让我们考虑一个测试字符串：

s='1test2345test'

对于大小为 4 的块，您的nChunks函数会给出以下输出：

>>>nChunks(s, step=4)
['1tes', 't234', '5tes', 't']

但你真正想要的是：

>>>def nChunks(iterable, start=0, step=1):
    return [iterable[i:i+step] for i in range(len(iterable)-step+1)]
>>>nChunks(s, step=4)
['1tes', 'test', 'est2', 'st23', 't234', '2345', '345t', '45te', '5tes', 'test']

你可以看到这样有两个'test'块，你patternFind(s)会像一个魅力一样工作：

>>> patternFind(s)
{'tes': 2, 'st': 2, 'te': 2, 'e': 2, 't': 4, 'es': 2, 'est': 2, 'test': 2, 's': 2}
于 2013-04-06T03:54:40.443 回答