python - 在大列表中搜索子字符串

Question

我试图找到两个字符串之间所有形式的插入。所以我有一个包含 1400 万个字符串的列表，然后我必须检查每个字符串哪些可能的插入可以将一个字符串转换为另一个字符串(基本上计算插入频率)。假设 x 是一个字符串，y 是另一个字符串，其中 x 是 y 的子字符串，因此我们必须找出哪些插入将 x 转换为 y。

我正在使用以下代码段。它有效，但需要花费很多时间。我什至尝试将负载分布到 64 个处理器上，但仍然需要 20 天才能完成。

for i in Words:
#trying to distribute load across different processes, so can ignore this part
   h = hashlib.sha256(i)
   n = int(h.hexdigest(),base=16)
   if (n%64!=ix): #ix is a process based id
    continue


   for j in Words:#
    if len(i)>len(j):
        continue
    if( i!=j and i in j):  # i is a substring of j
        ind=j.find(i)
        s1=j[0:ind]
        s2=j[ind+len(i):len(j)]

                    if(len(s1)>0):
            if (not transform.has_key(s1)):
                transform[s1]=1
            else:
                transform[s1]+=1

        if(len(s2)>0):
            if (not transform.has_key(s2)):
                transform[s2]=1
            else:
                transform[s2]+=1

Answer 1

不要将每个单词相互比较(二次运行时)，而是取每个单词的每个真子串(线性运行时，假设单词长度有界)并检查它是否在单词集中(查找 set 的元素)是常数时间)。

这在我的笔记本电脑上运行了不到 2 秒(46265 个单词(长度 < 10)和 47015 个唯一转换(总共 799089 个)):

from collections import Counter

# for testing
from random import choice, randrange
from string import ascii_uppercase
big_word = "".join(choice(ascii_uppercase) for i in range(10000))
words = [big_word[randrange(len(big_word)):][:randrange(1, 10)] for i in range(100000)] # words of up to 9 letters; all are substrings of big_word  

# now the real code
def insertions(words):
    for word in words:
        for i in range(1, len(word) - 1):
            ins = word[:i]
            rest = word[i:]
            for j in range(1, len(rest)):
                if rest[:j] in words:
                    yield ins
        for i in range(1, len(word) - 1):
            rest = word[:i]
            ins = word[i:]
            for j in range(len(rest) - 1):
                if rest[j:] in words:
                    yield ins

transforms = Counter(insertions(set(words)))