更快、更高效的 python 方法，用于模糊匹配子字符串

Question

我希望程序通过模糊匹配搜索所有出现的鳄鱼等，即如果有任何拼写错误，它也应该计算这些单词。

s="Difference between a crocodile and an alligator is......." #Long paragraph, >10000 words
to_search=["crocodile","insect","alligator"]
for i in range(len(to_search)):
for j in range(len(s)):
a = s[j:j+len(to_search[i])]
match = difflib.SequenceMatcher(None,a,to_search[I]).ratio()
if(match>0.9): #90% similarity
print(a)

因此，以下所有内容都应被视为"鳄鱼"的实例："鳄鱼"，"鳄鱼"，"鳄鱼"等

上述方法有效，但如果主字符串(此处为"s"(很大，例如>100 万个单词，则速度太慢。 有没有比上述方法更快的方法**？

**(将字符串拆分为子字符串大小的块，然后将子字符串与参考单词进行比较(

Answer 1

在大量文本上花费太长时间的原因之一是，您要在整个文本中多次重复滑动窗口，每次搜索一次。很多计算都是将你的单词与可能包含多个单词部分的相同长度的块进行比较。

如果你愿意假设你总是希望匹配单个单词，你可以将文本拆分为单词并与单词进行比较 - 更少的比较(单词数量，与从文本中每个位置开始的窗口相比(，并且拆分只需要执行一次，而不是针对每个搜索词。下面是一个示例：

to_search= ["crocodile", "insect", "alligator"]
s = "Difference between a crocodile and an alligator is" #Long paragraph, >10000 words
s_words = s.replace(".", " ").split(" ") # Split on spaces, with periods removed
for search_for in to_search:
for s_word in s_words:
match = difflib.SequenceMatcher(None, s_word, search_for).ratio()
if(match > 0.9):  #90% similarity
print(s_word)
continue      # no longer need to continue the search for this word!

这应该会给你显着的加速，希望它能解决你的需求！

祝您编码愉快！