Golang 计算字符串编辑距离 - Levenshtein 算法

Levenshtein 距离（编辑距离）是衡量两个字符串相似度的常用方法，表示将一个字符串转换成另一个字符串所需的最少编辑操作次数（插入、删除或替换字符）。

常用 Levenshtein 算法库

在 Go 中，有几个常用的 Levenshtein 距离计算库：

1. github.com/agnivade/levenshtein
2. github.com/texttheater/golang-levenshtein/levenshtein

1. 使用 agnivade/levenshtein

这是最轻量级的实现，只提供核心功能：

package main

import (
	"fmt"
	"github.com/agnivade/levenshtein"
)

func main() {
	str1 := "kitten"
	str2 := "sitting"
	
	distance := levenshtein.ComputeDistance(str1, str2)
	fmt.Printf("Levenshtein distance between '%s' and '%s' is %d\n", str1, str2, distance)
	
	// 输出: Levenshtein distance between 'kitten' and 'sitting' is 3
}

2. 使用 texttheater/golang-levenshtein

这个库提供了更多功能，包括计算相似度百分比：

package main

import (
	"fmt"
	"github.com/texttheater/golang-levenshtein/levenshtein"
)

func main() {
	str1 := "kitten"
	str2 := "sitting"
	
	options := levenshtein.DefaultOptions
	distance := levenshtein.DistanceForStrings([]rune(str1), []rune(str2), options)
	
	fmt.Printf("Levenshtein distance: %d\n", distance)
	
	// 计算相似度比率 (0-1)
	maxLen := max(len(str1), len(str2))
	similarity := 1 - float64(distance)/float64(maxLen)
	fmt.Printf("Similarity ratio: %.2f\n", similarity)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

自定义实现

如果你想了解算法原理，也可以自己实现：

package main

import "fmt"

func levenshteinDistance(s1, s2 string) int {
	m := len(s1)
	n := len(s2)
	
	// 创建一个二维数组来存储距离
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	
	// 初始化边界条件
	for i := 0; i <= m; i++ {
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	
	// 填充dp数组
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = min(
					dp[i-1][j]+1,   // 删除
					dp[i][j-1]+1,   // 插入
					dp[i-1][j-1]+1, // 替换
				)
			}
		}
	}
	
	return dp[m][n]
}

func min(nums ...int) int {
	m := nums[0]
	for _, num := range nums {
		if num < m {
			m = num
		}
	}
	return m
}

func main() {
	str1 := "kitten"
	str2 := "sitting"
	
	distance := levenshteinDistance(str1, str2)
	fmt.Printf("Custom Levenshtein distance: %d\n", distance)
}

性能比较

对于大多数应用场景，使用现成的库是更好的选择：

• agnivade/levenshtein 是最快的实现
• texttheater/golang-levenshtein 提供了更多功能
• 自定义实现适合学习算法原理

实际应用场景

Levenshtein 距离常用于：

1. 拼写检查
2. 模糊搜索
3. DNA序列比对
4. 自然语言处理
5. 数据清洗和匹配

选择哪个库取决于你的具体需求，如果只需要基本功能，agnivade/levenshtein 是最佳选择；如果需要更多功能如相似度计算，则选择 texttheater/golang-levenshtein。