快速高效的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”）的大小较大，如>；一百万字。 有没有比上述方法更快的方法

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

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!

这会给你显著的加速，希望它能解决你的需求

快乐编码