Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Part four of Levenshtein Distance
package main
import "fmt"
// PART FOUR: in which we get the min value for delete, insert, substitute and set value in Vector, return significant Vector value.
func MinInt(a ...int) int {
min := int(^uint(0) >> 1)
for _, i := range a {
if i < min {
min = i
}
}
return min
}
func LevenshteinThree(s1, s2 string) int {
m := len(s1)
n := len(s2)
width := n - 1
vcell := make([]int, m * n)
fmt.Println("initial",vcell)
// cells for i of m(s1)
for i := 1; i < m; i++ {
vcell[i * width + 0] = i
}
fmt.Println("i:",vcell)
// cell for j of n(s2)
for j := 1; j < n; j++ {
vcell[0 * width + j] = j
}
fmt.Println("j:",vcell)
count := 0
for j := 1; j < n; j++ {
for i := 1; i < m; i++ {
if s1[i] == s2[j] {
count += 1
vcell[i * width + j] = vcell[(i - 1) * width + (j - 1)]
fmt.Println("si[i] == s2[j]:",vcell, "count=",count)
} else {
deletion := vcell[(i - 1) * width + j] + 1
fmt.Println("deletion:",vcell)
insertion := vcell[(i * width + (j - 1))] + 1
fmt.Println("insert:",vcell)
substitution := vcell[((i - 1) * width + (j - 1))] + 1
fmt.Println("sub:",vcell)
vcell[i * width + j] = MinInt(deletion,insertion,substitution)
mind := (i * width + j)
count += 1
fmt.Println("Min:",vcell, "count=",count, "idx", mind)
}
}
}
fmt.Println("Done:",vcell, "final value",(m * width + 0))
return vcell[m * width + 0]
}
func main() {
fmt.Println(LevenshteinThree("stri","str"))
}
/*
*** OUTPUT
initial [0 0 0 0 0 0 0 0 0 0 0 0]
i: [0 0 1 0 2 0 3 0 0 0 0 0]
j: [0 1 2 0 2 0 3 0 0 0 0 0]
si[i] == s2[j]: [0 1 2 0 2 0 3 0 0 0 0 0] count= 1
deletion: [0 1 2 0 2 0 3 0 0 0 0 0]
insert: [0 1 2 0 2 0 3 0 0 0 0 0]
sub: [0 1 2 0 2 0 3 0 0 0 0 0]
Min: [0 1 2 0 2 1 3 0 0 0 0 0] count= 2 idx 5
deletion: [0 1 2 0 2 1 3 0 0 0 0 0]
insert: [0 1 2 0 2 1 3 0 0 0 0 0]
sub: [0 1 2 0 2 1 3 0 0 0 0 0]
Min: [0 1 2 0 2 1 3 2 0 0 0 0] count= 3 idx 7
deletion: [0 1 2 0 2 1 3 2 0 0 0 0]
insert: [0 1 2 0 2 1 3 2 0 0 0 0]
sub: [0 1 2 0 2 1 3 2 0 0 0 0]
Min: [0 1 2 0 1 1 3 2 0 0 0 0] count= 4 idx 4
si[i] == s2[j]: [0 1 2 0 1 1 0 2 0 0 0 0] count= 5
deletion: [0 1 2 0 1 1 0 2 0 0 0 0]
insert: [0 1 2 0 1 1 0 2 0 0 0 0]
sub: [0 1 2 0 1 1 0 2 0 0 0 0]
Min: [0 1 2 0 1 1 0 2 1 0 0 0] count= 6 idx 8
Done: [0 1 2 0 1 1 0 2 1 0 0 0] final value 8
1
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.