# [Golang] Wagner-Fischer algorithm for Edit Distance of Two Strings

Go implementation of Wagner-Fischer algorithm that computes the edit distance between two strings of characters. The edit distance here is Levenshtein distance, the minimum number of single-character edits (insertions, deletions or substitutions) required to change one string into the other.

The following code is utility for converting a string to rune slice, and minimum value of three integers.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | ```
package ld
func StringToRuneSlice(s string) []rune {
var r []rune
for _, runeValue := range s {
r = append(r, runeValue)
}
return r
}
func minimum(a, b, c int) int {
min := a
if min > b {
min = b
}
if min > c {
min = c
}
return min
}
``` |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | ```
package ld
// The edit distances here is actually Levenshtein distance, minimum number of
// single-character edits (insertions, deletions or substitutions) required to
// change one string into the other.
func EditDistance(s, t string) int {
ss := StringToRuneSlice(s)
m := len(ss) + 1
tt := StringToRuneSlice(t)
n := len(tt) + 1
d := make([][]int, m)
for i := range d {
d[i] = make([]int, n)
}
for i := 0; i < m; i++ {
d[i][0] = i
}
for j := 0; j < n; j++ {
d[0][j] = j
}
for j := 1; j < n; j++ {
for i := 1; i < m; i++ {
var substitutionCost int
if ss[i-1] == tt[j-1] {
substitutionCost = 0
} else {
substitutionCost = 1
}
d[i][j] = minimum(
d[i-1][j]+1,
d[i][j-1]+1,
d[i-1][j-1]+substitutionCost,
)
}
}
return d[m-1][n-1]
}
``` |

Testing:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | ```
package ld
import (
"testing"
)
func TestEditDistance(t *testing.T) {
if EditDistance("soccer", "otter") != 3 {
t.Error(`"soccer", "otter"`)
}
if EditDistance("你好他他是誰", "好我我是誰") != 3 {
t.Error(`"你好他他是誰", "好我我是誰"`)
}
if EditDistance("kitten", "sitten") != 1 {
t.Error(`"kitten", "sitten"`)
}
if EditDistance("sitten", "sittin") != 1 {
t.Error(`"sitten", "sittin"`)
}
if EditDistance("sittin", "sitting") != 1 {
t.Error(`"sittin", "sitting"`)
}
if EditDistance("sort", "some") != 2 {
t.Error(`"sort", "some"`)
}
if EditDistance("sort", "same") != 3 {
t.Error(`"sort", "same"`)
}
if EditDistance("sort", "soft") != 1 {
t.Error(`"sort", "soft"`)
}
}
``` |

For recursive implementation of Levenshtein distance, see [1].

Tested on:

`Ubuntu Linux 16.10`,`Go 1.8`- Go Playground.

References:

[1] | [Golang] Levenshtein Distance Recursive Implementation |

[2] | [Golang] Initialize Two Dimensional Array/Slice |

[3] | How do I know when recursive calls have all been completed? : golang |

[4] | How is infinite recursion and stack allocation controlled in Golang? : golang |