算法介紹

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