Go语言字符串相似度计算详解（从零实现Levenshtein编辑距离算法）

什么是字符串相似度？

字符串相似度通常通过编辑距离（Edit Distance）来衡量。最常见的编辑距离是Levenshtein距离，它表示将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。允许的操作包括：

• 插入一个字符
• 删除一个字符
• 替换一个字符

例如，将 "kitten" 转换为 "sitting" 需要 3 步：

1. kitten → sitten（替换 k 为 s）
2. sitten → sittin（替换 e 为 i）
3. sittin → sitting（插入 g）

因此，它们的 Levenshtein 距离是 3。

用Go语言实现Levenshtein算法

下面我们用 Go 语言编写一个函数来计算两个字符串之间的 Levenshtein 距离。我们将使用动态规划方法，这是最经典且高效的实现方式。

// levenshtein.gopackage mainimport (	"fmt")// 计算两个字符串之间的Levenshtein编辑距离func levenshteinDistance(s1, s2 string) int {	len1, len2 := len(s1), len(s2)	// 创建二维数组 dp，dp[i][j] 表示 s1[:i] 和 s2[:j] 的编辑距离	dp := make([][]int, len1+1)	for i := range dp {		dp[i] = make([]int, len2+1)	}	// 初始化边界条件	for i := 0; i <= len1; i++ {		dp[i][0] = i // 将 s1[:i] 变为空字符串需要 i 次删除	}	for j := 0; j <= len2; j++ {		dp[0][j] = j // 将空字符串变为 s2[:j] 需要 j 次插入	}	// 填充 dp 表	for i := 1; i <= len1; i++ {		for j := 1; j <= len2; j++ {			if s1[i-1] == s2[j-1] {				// 字符相同，不需要操作				dp[i][j] = dp[i-1][j-1]			} else {				// 取三种操作的最小值 + 1				deleteOp := dp[i-1][j] + 1     // 删除 s1[i-1]				insertOp := dp[i][j-1] + 1     // 插入 s2[j-1]				replaceOp := dp[i-1][j-1] + 1  // 替换 s1[i-1] 为 s2[j-1]				min := deleteOp				if insertOp < min {					min = insertOp				}				if replaceOp < min {					min = replaceOp				}				dp[i][j] = min			}		}	}	return dp[len1][len2]}// 计算相似度百分比（可选）func similarity(s1, s2 string) float64 {	if len(s1) == 0 && len(s2) == 0 {		return 1.0	}	maxLen := len(s1)	if len(s2) > maxLen {		maxLen = len(s2)	}	distance := levenshteinDistance(s1, s2)	return 1.0 - float64(distance)/float64(maxLen)}func main() {	s1 := "kitten"	s2 := "sitting"	dist := levenshteinDistance(s1, s2)	sim := similarity(s1, s2)	fmt.Printf("字符串 '%s' 和 '%s' 的编辑距离: %d\n", s1, s2, dist)	fmt.Printf("相似度: %.2f%%\n", sim*100)}

代码解析

上面的代码实现了两个核心函数：

• levenshteinDistance：返回两个字符串之间的编辑距离。
• similarity：基于编辑距离计算相似度百分比（值越接近1，越相似）。

运行结果如下：

字符串 'kitten' 和 'sitting' 的编辑距离: 3相似度: 57.14%

优化与扩展

上述实现的时间复杂度为 O(m×n)，空间复杂度也是 O(m×n)。如果只关心距离值而不需回溯路径，可以将空间复杂度优化到 O(min(m, n))，通过只保留两行数据来实现。

此外，你还可以考虑使用第三方库如 github.com/agext/levenshtein 来获得更高效的实现。

总结

通过本教程，你已经掌握了如何在 Go语言 中实现 字符串编辑距离 算法，并理解了 Levenshtein算法 的基本原理。这项技术在自然语言处理、数据清洗、生物信息学等领域有广泛应用。希望你能将所学应用到自己的项目中！

记住我们的四个核心 SEO关键词：Go语言字符串相似度、字符串编辑距离、Levenshtein算法Go实现、Go字符串比较。掌握这些概念，你就能在字符串处理领域游刃有余！