gpt4 book ai didi

python - 以比 n^2 更低的时间复杂度标记相似的句子

转载 作者:太空狗 更新时间:2023-10-30 02:23:30 25 4
gpt4 key购买 nike

这是我的第一篇文章,潜伏了很长时间,所以我会尽力在这里解释一下。

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

我想要的是对文本 block 进行某种预处理,以便在每次迭代时减少要匹配的帖子数量。也欢迎任何进一步的优化。

以下是我使用的相同功能。调用它们的主函数首先调用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,numOccurences)。然后,要找到可能与给定字符串相似的所有字符串,遍历它的单词并在倒排索引中查找包含该单词的字符串。这样您将获得一个表“(docId, wordMatchScore)”,该表自动仅包含 wordMatchScore 不为零的条目。

有大量可能的优化;此外,您的代码非常不理想,但如果我们谈论的是减少用于比较的字符串对的数量,那么就是这样。

关于python - 以比 n^2 更低的时间复杂度标记相似的句子,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3620318/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com