高效包含彼此的字符串

Question

我有两个字符串集合（A 和 B），我想找出所有的字符串对，其中 a 来自 A，b 来自 B，并且 a 是 b 的一部分。

编写这个代码的第一步是这样的：

for a in A:
    for b in B:
        if a in b:
            print (a,b)

不过，我想知道有没有更高效的方法来实现，比如用正则表达式（例如，不是检查 if a in b:，而是检查正则表达式 '.*' + a + '.*': 是否匹配 'b'。我觉得这样做可能会让我为所有的 a 缓存 Knuth-Morris-Pratt 的失败函数。而且，在内层的 for b in B: 循环中使用列表推导式可能会大大提高速度（甚至嵌套的列表推导式可能会更好）。

我并不太关心算法的渐进运行时间（比如使用后缀树或者其他复杂的聪明方法）。我更关心的是常数时间（我只需要对几个 A 和 B 的组合进行这个操作，不想让它跑一整周）。

你知道有什么技巧或者通用建议可以让这个过程更快吗？ 非常感谢你能分享的任何见解！

---

编辑：

根据 @ninjagecko 和 @Sven Marnach 的建议，我快速建立了一个10个字符的前缀表：

    import collections
    prefix_table = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i in xrange(len(prot_seq)-10):
            j = i+10+1
            prefix_table[b[i:j]].add(k)

    for a in A:
        if len(a) >= 10:
            for k in prefix_table[a[:10]]:
                # check if a is in b
                # (missing_edges is necessary, but not sufficient)
                if a in B[k]:
                    print (a,b)
        else:
            for k in xrange(len(prots_and_seqs)):
                # a is too small to use the table; check if
                # a is in any b
                if a in B[k]:
                    print (a, b)

相关问题：

• 查找重叠匹配项
• 在长的排序字符串列表中用Python快速查找'startswith'子串的方法
• 使用re.split在Python中将文件分割成行
• finditer在长字符串匹配时挂起
• 正则表达式负向前查找
• 匹配Python中以逗号分隔的AWS区域的正则表达式
• Python正则表达式中的%号单词边界
• 列表推导式移除仅包含数字（包含"_"或"-"）的Python列表元素

Answer 1

一种非常快速的搜索多个字符串的方法是使用有限自动机（所以你之前提到的正则表达式也不是完全错的），具体来说是Aho-Corasick字符串匹配机器，这种方法被很多工具使用，比如grep、病毒扫描器等。

首先，它会把你想要搜索的字符串（在你的例子中就是A中的单词）编译成一个有限状态自动机，并且带有失败函数（如果你对细节感兴趣，可以看看1975年的论文）。这个自动机会读取输入的字符串，并输出所有找到的搜索字符串（你可能想稍微修改一下，让它也输出包含搜索字符串的原始字符串）。

这种方法的好处是，它可以同时搜索所有的字符串，因此只需要对输入字符串的每个字符查看一次（线性复杂度）！

在上有Aho-Corasick模式匹配器的实现，不过我没有测试过，所以无法评价这些实现的性能、易用性或正确性。

---

编辑：我试用了这个 Aho-Corasick自动机的实现，确实是目前建议的方法中最快的，而且也很容易使用：

import pyahocorasick

def aho(A, B):
    t = pyahocorasick.Trie();
    for a in A:
        t.add_word(a, a)
    t.make_automaton()
    return [(s,b) for b in B for (i,res) in t.iter(b) for s in res]

不过我观察到，在用@SvenMarnach的脚本测试这个实现时，它的结果稍微少了一些，我不太确定原因。我给创建者发了邮件，也许他能找出问题所在。

Answer 2

假设你的单词长度是有限制的（比如说最多10个字母）。要实现线性时间复杂度，也就是 O(A+B)，可以按照以下步骤操作：

• 先初始化一个哈希表或者字典树（trie）
• 对于每个在B中的字符串b：
  • 对这个字符串的每个子字符串
    • 把这个子字符串添加到哈希表/字典树中，并记录它属于哪个字符串（这一步的复杂度不会超过 55*O(B)=O(B)）
• 对于每个在A中的字符串a：
  • 在你的哈希表/字典树中进行一次 O(1) 的查询，找出它包含的所有B字符串，然后返回这些结果

（在写这个回答的时候，还没有人确认OP的“单词”是否有限制。如果没有限制，这个方法仍然适用，但会有 O(maxwordsize^2) 的依赖。不过实际上在实践中效果会更好，因为并不是所有单词的长度都一样，所以可能会变成 O(averagewordsize^2)，如果分布合适的话。例如，如果所有单词都是20个字母，问题的复杂度会比10个字母时增加4倍。但如果只有少量单词从10个字母增加到20个字母，复杂度变化就不大。）

补充： https://stackoverflow.com/q/8289199/711085 实际上是一个理论上更好的答案。在那个答案发布之前，我在看相关的维基百科页面，当时觉得“字符串大小的线性复杂度并不是你想要的”，后来才意识到这正是你想要的。你构建正则表达式 (Aword1|Aword2|Aword3|...) 的直觉是对的，因为在后台生成的有限自动机如果支持同时重叠匹配，就能快速匹配，而并不是所有的正则表达式引擎都支持这一点。最终你应该使用什么，取决于你是否打算重复使用A或B，或者这只是一次性的需求。上面的方法实现起来更简单，但只有在你的单词长度有限制时才有效（如果不限制单词长度，会引入拒绝服务的风险），但如果你不想使用 Aho-Corasick 字符串匹配有限自动机 或类似的工具，或者没有可用的库，这可能是你需要的方案。

Answer 3

当然，你可以很简单地把这个写成一个列表推导式：

[(a, b) for a in A for b in B if a in b]

这样可能会稍微加快循环的速度，但不要期待太多。我觉得用正则表达式在这个问题上不会有什么帮助。

编辑：这里有一些时间记录：

import itertools
import timeit
import re
import collections

with open("/usr/share/dict/british-english") as f:
    A = [s.strip() for s in itertools.islice(f, 28000, 30000)]
    B = [s.strip() for s in itertools.islice(f, 23000, 25000)]

def f():
    result = []
    for a in A:
        for b in B:
            if a in b:
                result.append((a, b))
    return result

def g():
    return [(a, b) for a in A for b in B if a in b]

def h():
    res = [re.compile(re.escape(a)) for a in A]
    return [(a, b) for a in res for b in B if a.search(b)]

def ninjagecko():
    d = collections.defaultdict(set)
    for k, b in enumerate(B):
        for i, j in itertools.combinations(range(len(b) + 1), 2):
            d[b[i:j]].add(k)
    return [(a, B[k]) for a in A for k in d[a]]

print "Nested loop", timeit.repeat(f, number=1)
print "List comprehension", timeit.repeat(g, number=1)
print "Regular expressions", timeit.repeat(h, number=1)
print "ninjagecko", timeit.repeat(ninjagecko, number=1)

结果：

Nested loop [0.3641810417175293, 0.36279606819152832, 0.36295199394226074]
List comprehension [0.362030029296875, 0.36148500442504883, 0.36158299446105957]
Regular expressions [1.6498990058898926, 1.6494300365447998, 1.6480278968811035]
ninjagecko [0.06402897834777832, 0.063711881637573242, 0.06389307975769043]

编辑 2：我在时间记录中添加了一个变种，来自ninjagecko建议的算法。你可以看到它比所有的暴力破解方法要好得多。

编辑 3：我用集合代替了列表来消除重复项。（我没有更新时间记录——它们基本保持不变。）