Golang实现可定制编辑成本的Levenshtein距离计算

Levenshtein距离（编辑距离）是衡量两个字符串相似度的常用方法，表示将一个字符串转换成另一个字符串所需的最少单字符编辑操作（插入、删除、替换）次数。下面我将展示如何用Golang实现一个可定制编辑成本的Levenshtein距离计算库。

基础实现

首先，我们实现一个基础版本的Levenshtein距离计算：

package levenshtein

// BasicLevenshtein 计算基础Levenshtein距离
func BasicLevenshtein(a, b string) int {
	// 创建一个二维切片存储距离
	d := make([][]int, len(a)+1)
	for i := range d {
		d[i] = make([]int, len(b)+1)
	}

	// 初始化边界条件
	for i := 0; i <= len(a); i++ {
		d[i][0] = i
	}
	for j := 0; j <= len(b); j++ {
		d[0][j] = j
	}

	// 填充距离矩阵
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			cost := 0
			if a[i-1] != b[j-1] {
				cost = 1
			}
			d[i][j] = min(
				d[i-1][j]+1,   // 删除
				d[i][j-1]+1,   // 插入
				d[i-1][j-1]+cost, // 替换
			)
		}
	}

	return d[len(a)][len(b)]
}

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

可定制成本的实现

接下来，我们扩展这个实现，允许自定义不同操作的代价：

package levenshtein

// CostParams 定义编辑操作的代价
type CostParams struct {
	InsertCost  int // 插入代价
	DeleteCost  int // 删除代价
	ReplaceCost int // 替换代价
}

// DefaultCost 返回默认代价（所有操作代价为1）
func DefaultCost() CostParams {
	return CostParams{1, 1, 1}
}

// CustomLevenshtein 计算可定制成本的Levenshtein距离
func CustomLevenshtein(a, b string, cost CostParams) int {
	d := make([][]int, len(a)+1)
	for i := range d {
		d[i] = make([]int, len(b)+1)
	}

	// 初始化边界条件
	for i := 0; i <= len(a); i++ {
		d[i][0] = i * cost.DeleteCost
	}
	for j := 0; j <= len(b); j++ {
		d[0][j] = j * cost.InsertCost
	}

	// 填充距离矩阵
	for i := 1; i <= len(a); i++ {
		for j := 1; j <= len(b); j++ {
			replaceCost := 0
			if a[i-1] != b[j-1] {
				replaceCost = cost.ReplaceCost
			}
			d[i][j] = min(
				d[i-1][j]+cost.DeleteCost,
				d[i][j-1]+cost.InsertCost,
				d[i-1][j-1]+replaceCost,
			)
		}
	}

	return d[len(a)][len(b)]
}

相似度计算

基于Levenshtein距离，我们可以计算字符串相似度：

// Similarity 计算字符串相似度（0-1之间）
func Similarity(a, b string, cost CostParams) float64 {
	maxLen := max(len(a), len(b))
	if maxLen == 0 {
		return 1.0
	}
	distance := CustomLevenshtein(a, b, cost)
	maxPossible := max(
		len(a)*cost.DeleteCost+len(b)*cost.InsertCost,
		len(a)*cost.InsertCost+len(b)*cost.DeleteCost,
		len(a)*cost.ReplaceCost+abs(len(a)-len(b))*max(cost.InsertCost, cost.DeleteCost),
	)
	return 1.0 - float64(distance)/float64(maxPossible)
}

func max(nums ...int) int {
	m := nums[0]
	for _, n := range nums[1:] {
		if n > m {
			m = n
		}
	}
	return m
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

使用示例

package main

import (
	"fmt"
	"yourmodule/levenshtein"
)

func main() {
	str1 := "kitten"
	str2 := "sitting"

	// 使用默认成本
	basicDist := levenshtein.BasicLevenshtein(str1, str2)
	fmt.Printf("Basic Levenshtein distance: %d\n", basicDist)

	// 使用自定义成本
	customCost := levenshtein.CostParams{
		InsertCost:  1,
		DeleteCost:  1,
		ReplaceCost: 2, // 替换代价更高
	}
	customDist := levenshtein.CustomLevenshtein(str1, str2, customCost)
	fmt.Printf("Custom cost distance: %d\n", customDist)

	// 计算相似度
	similarity := levenshtein.Similarity(str1, str2, customCost)
	fmt.Printf("Similarity: %.2f\n", similarity)
}

性能优化

对于长字符串，我们可以优化空间复杂度，只使用两行而不是整个矩阵：

// OptimizedLevenshtein 空间优化的Levenshtein距离计算
func OptimizedLevenshtein(a, b string, cost CostParams) int {
	// 确保b是较短的字符串
	if len(a) < len(b) {
		a, b = b, a
	}

	prevRow := make([]int, len(b)+1)
	currentRow := make([]int, len(b)+1)

	// 初始化第一行
	for j := 0; j <= len(b); j++ {
		prevRow[j] = j * cost.InsertCost
	}

	for i := 1; i <= len(a); i++ {
		currentRow[0] = i * cost.DeleteCost
		for j := 1; j <= len(b); j++ {
			replaceCost := 0
			if a[i-1] != b[j-1] {
				replaceCost = cost.ReplaceCost
			}
			currentRow[j] = min(
				prevRow[j]+cost.DeleteCost,
				currentRow[j-1]+cost.InsertCost,
				prevRow[j-1]+replaceCost,
			)
		}
		// 交换行
		prevRow, currentRow = currentRow, prevRow
	}

	return prevRow[len(b)]
}

总结

这个实现提供了：

1. 基础Levenshtein距离计算
2. 可定制的编辑操作成本
3. 字符串相似度计算
4. 空间优化版本

你可以根据需要进一步扩展，比如添加：

• 阈值限制，当距离超过阈值时提前终止计算
• 支持Unicode字符
• 并行计算
• 缓存机制

这个库可以用于拼写检查、模糊搜索、DNA序列比对等多种场景。