LevenshteinDistance measures the difference between two strings. The Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other. This implementation is optimized to use O(min(m,n)) s
(s, t string)
| 22 | // optimized C version found here: |
| 23 | // http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#C |
| 24 | func levenshteinDistance(s, t string) int { |
| 25 | if len(s) > len(t) { |
| 26 | s, t = t, s |
| 27 | } |
| 28 | r1, r2 := []rune(s), []rune(t) // len(s) <= len(t) => len(r1) <= len(r2) |
| 29 | column := make([]int, len(r1)+1) |
| 30 | |
| 31 | for y := 1; y <= len(r1); y++ { |
| 32 | column[y] = y |
| 33 | } |
| 34 | |
| 35 | for x := 1; x <= len(r2); x++ { |
| 36 | column[0] = x |
| 37 | |
| 38 | for y, lastDiag := 1, x-1; y <= len(r1); y++ { |
| 39 | oldDiag := column[y] |
| 40 | cost := 0 |
| 41 | if r1[y-1] != r2[x-1] { |
| 42 | cost = 1 |
| 43 | } |
| 44 | column[y] = min(column[y]+1, column[y-1]+1, lastDiag+cost) |
| 45 | lastDiag = oldDiag |
| 46 | } |
| 47 | } |
| 48 | return column[len(r1)] |
| 49 | } |
| 50 | |
| 51 | func min(a, b, c int) int { |
| 52 | if a < b && a < c { |