Golang program for implementation of Levenshtein distance
Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t. For example, the Levenshtein distance between "Asheville" and "Arizona" is 8.
Here is source code of the Go Program to Implement Levenshtein Distance Computing Algorithm.
Example
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))
}
Output
Distance between Asheville and Arizona: 8
Distance between Python and Peithen: 3
Distance between Orange and Apple: 5
Most Helpful This Week
How to Convert string to integer type in Go?
Golang program for implementation of Selection Sort
How do you send an HTTP PUT request in Go?
How to copy one slice items into another slice in Golang?
Comparing Structs with the Different Values Assigned to Data Fields
GO language program with example of Array Reverse Sort Functions for integer and strings