在一组字符串中查找子字符串

Question

我有一个包含50,000到100,000个字符串的集合mystrings。其中一些字符串可能是其他字符串的精确子字符串，我想将它们合并（丢弃子字符串并只保留最长的字符串）。目前我正在使用一种朴素的方法，其时间复杂度为O(N^2)。

unique_strings = set()
for s in sorted(mystrings, key=len, reverse=True):
    keep = True
    for us in unique_strings:
        if s in us:
            keep = False
            break
    if keep:
        unique_strings.add(s)

哪些数据结构或算法可以让这个任务更容易，而且不需要 O(N^2) 的操作。使用库是可以的，但我需要保持纯Python。

- Daniel Standage

---

更加Pythonic，丢弃keep布尔值，改用for循环中的else子句（当然不会改变时间复杂度）。http://python-notes.curiousefficiency.org/en/latest/python_concepts/break_else.html - Chris_Rands

@Chris_Rands 你能演示一下吗？一旦找到匹配项，就没有继续迭代内部循环的理由，因此使用了break。但是，一旦我们跳出内部循环，我们无法确定是因为找到了匹配项还是因为完成了迭代。也许我有所遗漏，但我认为这是实现这种（虽然天真）方法最简洁和高效的方式。 - Daniel Standage

保留 break，只需将 if keep: 替换为 else:（缩进相同），并删除所有带有 keep 的行。当 break 不发生时，才会执行 else 子句。如果您不熟悉 for-else 结构，请阅读我上面链接的文章。 - Chris_Rands

太酷了！这些关键词如此常见，我忽略了循环的语义含义。 - Daniel Standage

事实上，重新审视一下，你可以使用any()或者all()代替，像这样：if not any(s in us for us in unique_strings): unique_strings.add(s) 它会像break一样短路。 - Chris_Rands

Answer 1

在set()中查找子字符串：

name = set()
name.add('Victoria Stuart')                         ## add single element
name.update(('Carmine Wilson', 'Jazz', 'Georgio'))  ## add multiple elements
name
{'Jazz', 'Georgio', 'Carmine Wilson', 'Victoria Stuart'}

me = 'Victoria'
if str(name).find(me):
    print('{} in {}'.format(me, name))
# Victoria in {'Jazz', 'Georgio', 'Carmine Wilson', 'Victoria Stuart'}

那很容易--但如果你想返回匹配的字符串，这有些棘手：

for item in name:
    if item.find(me):
            print(item)
'''
Jazz
Georgio
Carmine Wilson
'''

print(str(name).find(me))
# 39    ## character offset for match (i.e., not a string)

正如您所看到的，上面的循环仅在条件为True时执行，终止并未打印我们想要的项目（匹配的字符串）。

使用正则表达式可能会更好、更容易:

import re

for item in name:
    if re.match(me, item):
            full_name = item
            print(item)
# Victoria Stuart
print(full_name)
# Victoria Stuart

for item in name:
    if re.search(me, item):
            print(item)
# Victoria Stuart

来自Python文档:

search() vs. match()

Python基于正则表达式提供了两种不同的原始操作：re.match()仅在字符串开头检查匹配，而re.search()检查在字符串中任何位置是否有匹配...

- Victoria Stuart

Answer 2

您可以对字符串进行预排序，并创建一个将字符串映射到排序列表中位置的字典。然后，您可以循环遍历字符串（O(N)）和后缀（O(L)）列表，并将存在于位置字典中的条目设置为None（O(1)字典查找和O(1)列表更新）。因此，总体复杂度为O(N*L)，其中L是平均字符串长度。

strings = sorted(mystrings, key=len, reverse=True)
index_map = {s: i for i, s in enumerate(strings)}
unique = set()
for i, s in enumerate(strings):
    if s is None:
        continue
    unique.add(s)
    for k in range(1, len(s)):
        try:
            index = index_map[s[k:]]
        except KeyError:
            pass
        else:
            if strings[index] is None:
                break
            strings[index] = None

在以下示例数据上进行测试可获得约21倍的加速比：

import random
from string import ascii_lowercase

mystrings = [''.join(random.choices(ascii_lowercase, k=random.randint(1, 10)))
             for __ in range(1000)]
mystrings = set(mystrings)

- a_guest

Answer 3

与此同时，我想出了这种方法。

from Bio.trie import trie
unique_strings = set()
suffix_tree = trie()
for s in sorted(mystrings, key=len, reverse=True):
    if suffix_tree.with_prefix(contig) == []:
        unique_strings.add(s)
        for i in range(len(s)):
            suffix_tree[s[i:]] = 1

好的方面：对于我正在处理的数据集，从约15分钟缩短到了约20秒。不好的方面：引入了biopython作为依赖项，这既不轻量级也不是纯Python（正如我最初所要求的）。

- Daniel Standage

Answer 4

一个朴素的方法：

1. sort strings by length, longest first  # `O(N*log_N)`
2. foreach string:  # O(N)
    3. insert each suffix into tree structure: first letter -> root, and so on.  
       # O(L) or O(L^2) depending on string slice implementation, L: string length
    4. if inserting the entire string (the longest suffix) creates a new 
       leaf node, keep it!

O[N*(log_N + L)]  or  O[N*(log_N + L^2)]

这可能远非最优，但对于大量字符串（N）和小平均字符串长度（L），应该比O(N^2)显着更好。

您还可以按长度降序迭代字符串，并将每个字符串的所有子字符串添加到集合中，仅保留不在集合中的字符串。算法的大O应与上述最坏情况相同（O[N*(log_N + L^2)]），但实现要简单得多：

seen_strings, keep_strings = set(), set()
for s in sorted(mystrings, key=len, reverse=True):
    if s not in seen_strings:
        keep_strings.add(s)
        l = len(s)
        for start in range(0, l-1):
            for end in range(start+1, l):
                seen_strings.add(s[start:end])

- user2390182