87 lines
1.8 KiB
Go
87 lines
1.8 KiB
Go
|
/*
|
|||
|
|
使用编辑距离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
|
|||
|
|
}
|