算法介绍

Jaccard 算法介绍(适用于长文本)

1.Jaccard 相似度(Jaccard similarity),也称为 Jaccard 指数或 Jaccard 系数, 是一种用于衡量两个集合相似度(可以通过 ngram 进行分词)的统计量. 其定义为两个集合的交集与并集的比值。它主要用于计算集合间的相似度, 广泛应用于信息检索/文本分析/图像处理等领域.
2.具体来说，给定两个集合 A 和 𝐵, Jaccard 相似度 𝐽(𝐴,𝐵) 定义为:

J(A,B)= ∣A ∩ B∣ / ∣A u B∣

// ∣A∩B∣ 表示集合 A 和 B 的交集元素的数量。
// ∣AuB∣ 表示集合 A 和 B 的并集元素的数量。

3.Jaccard 相似度的取值范围在 0 到 1 之间:

// 当时 𝐽(𝐴,𝐵) = 1，表示两个集合完全相同
// 当时 𝐽(𝐴,𝐵) = 0，表示两个集合完全不相同

Levenshtein 算法介绍(适用于短文本)

1.Levenshtein 距离 (Levenshtein distance) 也称为编辑距离 (edit distance) 是一种用于衡量两个字符串之间相似度的度量方法. 它定义为将一个字符串转换为另一个字符串所需的最少编辑操作次数. 允许的编辑操作包括插入一个字符/删除一个字符/替换一个字符.
2.处理如下:

// 假设有两个字符串：
s1 = "kitten"
s2 = "sitting"
// 计算它们的 Levenshtein 距离：

// 将 "k" 替换为 "s": kitten -> sitten （1 次操作）
// 将 "e" 替换为 "i": sitten -> sittin （1 次操作）
// 在末尾插入 "g": sittin -> sitting （1 次操作）
// 因此, Levenshtein 距离
Levenshtein("kitten","sitting")=3

// 相似度 (maxLen-Levenshtein)/maxLen
maxLen=max(s1.length, s2.length)
res=(maxLen-3)/maxLen