Go语言教程之边写边学：数据结构与算法：Levenshtein Distance编辑距离

编辑距离是针对二个字符串(例如英文字)的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个(或哪几个)是比较可能的字。DNA也可以视为用A、C、G和T组成的字符串，因此编辑距离也用在生物信息学中，判断二个DNA的类似程度。Unix下的diff及patch即是利用编辑距离来进行文本编辑对比的例子。

示例代码：

package main
import "fmt"

func levenshtein(str1, str2 []rune) int {
	s1len := len(str1)
	s2len := len(str2)
	column := make([]int, len(str1)+1)

	for y := 1; y <= s1len; y++ {
		column[y] = y
	}
	for x := 1; x <= s2len; x++ {
		column[0] = x
		lastkey := x - 1
		for y := 1; y <= s1len; y++ {
			oldkey := column[y]
			var incr int
			if str1[y-1] != str2[x-1] {
				incr = 1
			}

			column[y] = minimum(column[y]+1, column[y-1]+1, lastkey+incr)
			lastkey = oldkey
		}
	}
	return column[s1len]
}

func minimum(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
	} else {
		if b < c {
			return b
		}
	}
	return c
}

func main(){
	var str1 = []rune("Asheville")
	var str2 = []rune("Arizona")
	fmt.Println("Distance between Asheville and Arizona:",levenshtein(str1,str2))
	
	str1 = []rune("Python")
	str2 = []rune("Peithen")
	fmt.Println("Distance between Python and Peithen:",levenshtein(str1,str2))
	
	str1 = []rune("Orange")
	str2 = []rune("Apple")
	fmt.Println("Distance between Orange and Apple:",levenshtein(str1,str2))
}

输出：

Distance between Asheville and Arizona: 8
Distance between Python and Peithen: 3
Distance between Orange and Apple: 5