标记时间复杂度低于n^2的相似句子

这是我的第一个帖子,已经潜伏了很长一段时间,所以我会尽我最大的努力在这里解释我自己。

我一直在使用最常用的子串方法以及基本的单词匹配和子串匹配(regexp)来集群网络上类似的故事。 但问题是它的时间复杂度是n^2(我将每个标题与其他标题进行比较)。 我已经完成了非常基本的优化,比如存储和跳过所有匹配的标题。

我想要的是对文本块进行某种预处理,以便每次迭代都减少要匹配的文章数量。也欢迎进一步的优化。

下面是我用于相同的函数。调用它们的主函数首先调用单词“match”,如果超过70%的单词匹配,我将进一步向下调用“substring”和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