python - 如何在python中具有相似性得分的大字符串中找到相似的子串？

Question

我正在寻找的不仅仅是两个文本之间的简单相似度分数。但是字符串中子字符串的相似度得分。说:

text1 = 'cat is sleeping on the mat'.

text2 = 'The cat is sleeping on the red mat in the living room'.

在上面的例子中，text1中的所有单词都完整地出现在了text2中，因此相似度应该是100%。

如果text1部分单词缺失，则得分较低。

我正在处理一个具有不同段落大小的大型数据集，因此在具有如此相似性得分的较大段落中找到较小的段落至关重要。

我只发现了比较两个字符串的字符串相似性，例如余弦相似性、difflib 相似性等。但不是关于另一个字符串中的子字符串分数。

Answer 1

根据您的描述，如何:

>>> 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 中获益。相似性，我怀疑在这种情况下作为所提供解决方案的补充可能会有一些用处。