Go 语言 Levenshtein 编辑距离算法实现

完整实现代码

// ===================================== // file: distance/levenshtein.go // ===================================== package distance

// DistanceCalculator 编辑距离计算器
type DistanceCalculator struct{}

// NewDistanceCalculator 构造函数
func NewDistanceCalculator() *DistanceCalculator {
	return &DistanceCalculator{}
}

// -------------------------------------------------- // 标准二维动态规划版本（推荐教学版） // --------------------------------------------------
func (d *DistanceCalculator) Levenshtein(a, b string) int {
	ra := []rune(a)
	rb := []rune(b)
	m := len(ra)
	n := len(rb)
	// 创建二维 DP 数组
	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 ra[i-1] == rb[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]
}

// -------------------------------------------------- // 空间优化版本（滚动数组） // 空间复杂度 O(min(m,n)) // --------------------------------------------------
func (d *DistanceCalculator) LevenshteinOptimized(a, b string) int {
	ra := []rune(a)
	rb := []rune(b)
	if len(ra) < len(rb) {
		ra, rb = rb, ra
	}
	m := len(ra)
	n := len(rb)
	prev := make([]int, n+1)
	curr := make([]int, n+1)
	for j := 0; j <= n; j++ {
		prev[j] = j
	}
	for i := 1; i <= m; i++ {
		curr[0] = i
		for j := 1; j <= n; j++ {
			if ra[i-1] == rb[j-1] {
				curr[j] = prev[j-1]
			} else {
				curr[j] = min(prev[j]+1, curr[j-1]+1, prev[j-1]+1)
			}
		}
		prev, curr = curr, prev
	}
	return prev[n]
}

// min 辅助函数
func min(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	}
	if b < c {
		return b
	}
	return c
}

// ===================================== // file: main.go // =====================================
package main

import (
	"fmt"
	"distance/distance"
)

func main() {
	calculator := distance.NewDistanceCalculator()
	fmt.Println("标准版本:")
	fmt.Println(calculator.Levenshtein("kitten", "sitting"))
	fmt.Println("优化版本:")
	fmt.Println(calculator.LevenshteinOptimized("flaw", "lawn"))
	fmt.Println("Unicode 测试:")
	fmt.Println(calculator.Levenshtein("你好", "您好"))
}

代码解读

Levenshtein

• 使用二维 DP 数组
• 完整保存状态
• 易于理解
• 适合教学

LevenshteinOptimized

• 使用滚动数组
• 只保存上一行数据
• 空间复杂度降低
• 适合生产环境

min 函数

• 返回三个数的最小值
• 用于状态转移

总结

本项目实现：

• 标准二维 DP 版本
• 空间优化版本
• Unicode 安全版本
• 企业级封装结构

时间复杂度：O(m * n) 空间复杂度：

• 标准版：O(m * n)
• 优化版：O(min(m, n))

常见问题

Q1 为什么必须使用 []rune？

因为 Go 字符串是 UTF-8。中文字符占多个字节。如果用 byte 会出错。

Q2 是否可以支持权重不同？

可以。将 +1 替换为 +cost 即可实现加权编辑距离。

Q3 是否可以优化时间复杂度？

在一般情况下无法突破 O(m*n)。但可以提前剪枝或使用带阈值的算法。

扩展方向

1 Damerau-Levenshtein 距离

增加操作：相邻字符交换。

2 构建拼写纠错系统

结合字典、Trie 树、编辑距离阈值。

3 模糊搜索系统

用于搜索引擎、商品匹配、用户名检测。

4 生物信息学应用

用于 DNA 序列匹配、蛋白质序列分析。