python - 用比n ^ 2低的时间复杂性标记相似的句子

这是我的第一篇文章，很长时间以来都是一名编辑，所以我会尽力在这里向大家说明我自己。
我一直在使用最低公共子串方法以及基本单词匹配和子串匹配（ReGEXP）来在网络上聚类相似的故事。
但问题是它的时间复杂度是n 2（我将每个标题与其他所有的标题进行比较）。
我已经做了非常基本的优化，比如存储和跳过所有匹配的标题。
我想要的是对文本块的某种预处理，以便在每次迭代中减少与之匹配的帖子数量。任何进一步的优化也是值得欢迎的。
下面是我使用的函数。调用它们的主函数首先调用word_match，如果超过70%的单词匹配，则进一步向下调用“substring_match”和lcsubstr_len。代码是用python编写的，我也可以使用c

import re

def substring_match(a,b):
    try:
        c = re.match(a,b)
        return c if c else True if re.match(b,a) else False
    except:
        return False

def LCSubstr_len(S, T):
    m = len(S); n = len(T)
    L = [[0] * (n+1) for i in xrange(m+1)]
    lcs = 0
    for i in xrange(m):
     for j in xrange(n):
         if S[i] == T[j]:
             L[i+1][j+1] = L[i][j] + 1
             lcs = max(lcs, L[i+1][j+1])
         else:
             L[i+1][j+1] = max(L[i+1][j], L[i][j+1])
    return lcs/((float(m+n)/2))

def word_match(str1,str2):
    matched = 0
    try:
        str1,str2 = str(str1),str(str2)
        assert isinstance(str1,str)
    except:
        return 0.0
    words1 = str1.split(None)
    words2 = str2.split(None)
    for i in words1:
        for j in words2:
            if i.strip() ==j.strip():
                matched +=1
    len1 = len(words1)
    len2 = len(words2)
    perc_match = float(matched)/float((len1+len2)/2)
    return perc_match

最佳答案

使用倒排索引：对于每个单词，存储一个成对的列表（docid、numoccuremens）。
然后，为了查找可能与给定字符串相似的字符串，请遍历其单词并在倒置索引中查找包含该单词的字符串。这样您将得到一个表“（docid，wordmatchscore）”，它自动只包含wordmatchscore非零的条目。
还有大量的可能的优化；另外，您的代码非常不优化，但是如果我们讨论减少字符串对的数量来进行比较，那么就是这样。