设想一下以下的场景：
１、在游戏中聊天，我们想要避免玩家不断地用相同的内容或只做微小调整的内容进行刷屏。我们需要判断玩家每次发的消息与过去几次的相似程度。
２、在搜索引擎中，当用户输错内容时，程序能够进行检测，将正确的内容提示给用户。
如何实现这样的需求呢？
这样的需求的本质，其实是判断字符串之间的相似程度。在上面的两个场景中：
１、我们在内存中保存玩家最近发送的１０条消息，当玩家发送新的消息时；拿着新消息与历史消息进行逐一地匹配，判断它们之间的相似度，当相似度达到一定比例时，就可以拒绝玩家发送新的消息。
２、当玩家搜索时，我们可以使用Trie树来查询以玩家输入为前缀的内容；如果查询不到，则代表着玩家可能输入有误。这时，可以回退一些字符，获得匹配的内容的列表。此时，再逐一计算列表中的内容与用户输入内容的相似度，将相似度最大的内容推荐给用户。
而要衡量两个字符串的相似度，就需要用到编辑距离（Edit Distance）。
编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。
在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词之间，由其中一个单词转换为另一个单词所需要的最少单字符编辑操作次数。
在这里定义的单字符编辑操作有且仅有三种：
- 插入（Insertion）
- 删除（Deletion）
- 替换（Substitution）
譬如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "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 。
而实现编辑距离的最经典的方式就是使用动态规划（Dynamic Programming）。代码如下：
/*
使用编辑距离Edit Distance的方式来计算两个字符串的相似类。
参考资料：https://en.wikipedia.org/wiki/Edit_distance
*/
package stringUtil
// 计算两个字符串的相似度
// word1: 第一个字符串
// word2: 第二个字符串
// 返回值:
// 两个字符串的距离，表示两个字符串经过多少次变换，可以变成同一个字符串
// 两个字符串的相似度，范围为[0, 1]
func Similarity(word1, word2 string) (distance int, similarity float64) {
// 内部方法，用于计算最小值、最大值
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
}
// 如果有单词为空，或者单词相同，则直接计算出结果，无需进一步计算
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
}
// 使用动态规划计算编辑距离(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
