python - 相互包含的高效字符串

Question

我有两组字符串(A 和B)，我想知道所有字符串对 a in A 和 b in 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-mers 的快速前缀表:

    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)

Answer 1

当然你可以很容易地把它写成一个列表理解:

[(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:添加了 alogrithm suggested by ninjagecko 的变体到时间。您可以看到它比所有的蛮力方法都要好得多。

编辑 3:使用集合而不是列表来消除重复项。 (我没有更新时间——它们基本上保持不变。)