在python中,如何在具有相似性分数的大字符串中找到相似的子字符串?

根据您的描述,您认为:

>>> a = "cat is sleeping on the mat"
>>> b = "the cat is sleeping on the red mat in the living room"
>>> a = a.split(" ")
>>> score = 0.0
>>> for word in a: #for every word in your string
        if word in b: #if it is in your bigger string increase score
            score += 1
>>> score/len(a) #obtain percentage given total word number
1.0

如果缺少一个单词,例如:

>>> c = "the cat is not sleeping on the mat"
>>> c = c.split(" ")
>>> score = 0.0
>>> for w in c:
        if w in b:
            score +=1
>>> score/len(c)
0.875

此外,您还可以按照@roadrunner的建议进行拆分 b 并将其另存为一组,以加快性能 b = set(b.split(" ")) . 这将使该零件的复杂性降低到 O(1) 并将整体算法改进为 O(n) 复杂性

编辑: 您说您已经尝试了一些度量,如余弦相似性等。但是我怀疑您可能会从检查 Levenshtein Distance 相似性,我怀疑在这种情况下,除了提供的解决方案之外,还可以使用相似性。

您也可以使用 collections.defaultdict 将字数存储在 word_a 存在于 word_b 然后 sum() 计数除以 word\u a 最后:

from collections import defaultdict

a = "the cat is not sleeping on the mat"
b = "the cat is sleeping on the red mat in the living room"

word_a = a.split()
word_b = set(b.split())

d = defaultdict(int)
for word in word_a:
    if word in word_b:
        d[word] += 1

print(sum(d.values()) / len(word_a))

其输出:

0.875

注: 因为我们只关心 word\u a 存在于 word\u b ,然后转换 word\u b 到a set() 将允许 O(1) 查找,而不是保留一个列表 O(n) . 这使得上述代码的总体时间复杂度 O(n) .

与DarkCygbus相似,但相似性基于其计数总字符而不是单词。另一方面,此脚本只检查了与完整单词的一致性(text\u 2.split())

from __future__ import division

text_1 = 'cat is sleeping on the mat'
text_2 = 'The cat is sleeping on the red mat in the living room'
no_match = 0
match = 0

for word in text_1.split():
    if word not in text_2.split():
        no_match += len(word)
    else:
        match += len(word)

similarity = match/(match + no_match)
print ('{0:.0%}'.format(similarity))