設(shè)想一下以下的場景：
１抑片、在游戲中聊天睹栖，我們想要避免玩家不斷地用相同的內(nèi)容或只做微小調(diào)整的內(nèi)容進(jìn)行刷屏硫惕。我們需要判斷玩家每次發(fā)的消息與過去幾次的相似程度。
２野来、在搜索引擎中恼除，當(dāng)用戶輸錯內(nèi)容時，程序能夠進(jìn)行檢測曼氛，將正確的內(nèi)容提示給用戶豁辉。
如何實現(xiàn)這樣的需求呢？
這樣的需求的本質(zhì)舀患，其實是判斷字符串之間的相似程度徽级。在上面的兩個場景中：
１、我們在內(nèi)存中保存玩家最近發(fā)送的１０條消息聊浅，當(dāng)玩家發(fā)送新的消息時灰追；拿著新消息與歷史消息進(jìn)行逐一地匹配，判斷它們之間的相似度狗超，當(dāng)相似度達(dá)到一定比例時弹澎，就可以拒絕玩家發(fā)送新的消息。
２努咐、當(dāng)玩家搜索時苦蒿，我們可以使用Trie樹來查詢以玩家輸入為前綴的內(nèi)容；如果查詢不到渗稍，則代表著玩家可能輸入有誤佩迟。這時团滥，可以回退一些字符，獲得匹配的內(nèi)容的列表报强。此時灸姊，再逐一計算列表中的內(nèi)容與用戶輸入內(nèi)容的相似度，將相似度最大的內(nèi)容推薦給用戶秉溉。
而要衡量兩個字符串的相似度力惯，就需要用到編輯距離（Edit Distance）。
編輯距離（Minimum Edit Distance召嘶，MED）父晶，由俄羅斯科學(xué)家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance弄跌。
在信息論甲喝、語言學(xué)和計算機(jī)科學(xué)領(lǐng)域，Levenshtein Distance 是用來度量兩個序列相似程度的指標(biāo)铛只。通俗地來講埠胖，編輯距離指的是在兩個單詞之間，由其中一個單詞轉(zhuǎn)換為另一個單詞所需要的最少單字符編輯操作次數(shù)淳玩。
在這里定義的單字符編輯操作有且僅有三種：
- 插入（Insertion）
- 刪除（Deletion）
- 替換（Substitution）
譬如直撤，"kitten" 和 "sitting" 這兩個單詞，由 "kitten" 轉(zhuǎn)換為 "sitting" 需要的最少單字符編輯操作有：
1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end)
因此凯肋，"kitten" 和 "sitting" 這兩個單詞之間的編輯距離為 3 。
而實現(xiàn)編輯距離的最經(jīng)典的方式就是使用動態(tài)規(guī)劃（Dynamic Programming）汽馋。代碼如下：
/*
使用編輯距離Edit Distance的方式來計算兩個字符串的相似類侮东。
參考資料：https://en.wikipedia.org/wiki/Edit_distance
*/
package stringUtil
// 計算兩個字符串的相似度
// word1: 第一個字符串
// word2: 第二個字符串
// 返回值:
// 兩個字符串的距離，表示兩個字符串經(jīng)過多少次變換豹芯，可以變成同一個字符串
// 兩個字符串的相似度悄雅，范圍為[0, 1]
func Similarity(word1, word2 string) (distance int, similarity float64) {
// 內(nèi)部方法，用于計算最小值铁蹈、最大值
min := func(nums ...int) int {
_min := nums[0]
for _, v := range nums {
if v < _min {
_min = v
}
}
return _min
}
max := func(nums ...int) int {
_max := nums[0]
for _, v := range nums {
if v > _max {
_max = v
}
}
return _max
}
// 如果有單詞為空宽闲，或者單詞相同，則直接計算出結(jié)果握牧，無需進(jìn)一步計算
m, n := len(word1), len(word2)
if m == 0 {
distance = n
return
}
if n == 0 {
distance = m
return
}
if m == n && word1 == word2 {
distance = 0
similarity = 1
return
}
// 使用動態(tài)規(guī)劃計算編輯距離(Edit Distance)
// Step 1: define the data structure
dp := make([][]int, m+1, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]int, n+1, n+1)
}
// Step 2: init the data
for i := 0; i <= m; i++ {
for j := 0; j <= n; j++ {
if i == 0 {
dp[i][j] = j
}
if j == 0 {
dp[i][j] = i
}
}
}
// Step 3: state transition equation
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
}
}
// 得到距離并計算相似度
distance = dp[m][n]
maxLength := max(m, n)
similarity = float64(maxLength-distance) / float64(maxLength)
return
}
完整的代碼容诬，請參考：https://github.com/Jordanzuo/goutil/blob/master/stringUtil/similarity.go
