aboutsummaryrefslogtreecommitdiffstats
path: root/vendor/github.com/agnivade/levenshtein/levenshtein.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/agnivade/levenshtein/levenshtein.go')
-rw-r--r--vendor/github.com/agnivade/levenshtein/levenshtein.go71
1 files changed, 71 insertions, 0 deletions
diff --git a/vendor/github.com/agnivade/levenshtein/levenshtein.go b/vendor/github.com/agnivade/levenshtein/levenshtein.go
new file mode 100644
index 00000000..e215813f
--- /dev/null
+++ b/vendor/github.com/agnivade/levenshtein/levenshtein.go
@@ -0,0 +1,71 @@
+// Package levenshtein is a Go implementation to calculate Levenshtein Distance.
+//
+// Implementation taken from
+// https://gist.github.com/andrei-m/982927#gistcomment-1931258
+package levenshtein
+
+// ComputeDistance computes the levenshtein distance between the two
+// strings passed as an argument. The return value is the levenshtein distance
+//
+// Works on runes (Unicode code points) but does not normalize
+// the input strings. See https://blog.golang.org/normalization
+// and the golang.org/x/text/unicode/norm pacage.
+func ComputeDistance(a, b string) int {
+ if a == b {
+ return 0
+ }
+
+ // We need to convert to []rune if the strings are non-ascii.
+ // This could be avoided by using utf8.RuneCountInString
+ // and then doing some juggling with rune indices.
+ // The primary challenge is keeping track of the previous rune.
+ // With a range loop, its not that easy. And with a for-loop
+ // we need to keep track of the inter-rune width using utf8.DecodeRuneInString
+ s1 := []rune(a)
+ s2 := []rune(b)
+
+ // swap to save some memory O(min(a,b)) instead of O(a)
+ if len(s1) > len(s2) {
+ s1, s2 = s2, s1
+ }
+ lenS1 := len(s1)
+ lenS2 := len(s2)
+
+ // init the row
+ x := make([]int, lenS1+1)
+ for i := 0; i <= lenS1; i++ {
+ x[i] = i
+ }
+
+ // fill in the rest
+ for i := 1; i <= lenS2; i++ {
+ prev := i
+ var current int
+
+ for j := 1; j <= lenS1; j++ {
+
+ if s2[i-1] == s1[j-1] {
+ current = x[j-1] // match
+ } else {
+ current = min(x[j-1]+1, prev+1, x[j]+1)
+ }
+ x[j-1] = prev
+ prev = current
+ }
+ x[lenS1] = prev
+ }
+ return x[lenS1]
+}
+
+func min(a, b, c int) int {
+ if a < b {
+ if a < c {
+ return a
+ }
+ } else {
+ if b < c {
+ return b
+ }
+ }
+ return c
+}