aboutsummaryrefslogtreecommitdiff
path: root/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go')
-rw-r--r--vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go43
1 files changed, 0 insertions, 43 deletions
diff --git a/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go b/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go
deleted file mode 100644
index 237923d..0000000
--- a/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go
+++ /dev/null
@@ -1,43 +0,0 @@
-package fuzzy
-
-// 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 implemention is optimized to use O(min(m,n)) space and is based on the
-// optimized C version found here:
-// http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#C
-func LevenshteinDistance(s, t string) int {
- r1, r2 := []rune(s), []rune(t)
- column := make([]int, len(r1)+1)
-
- for y := 1; y <= len(r1); y++ {
- column[y] = y
- }
-
- for x := 1; x <= len(r2); x++ {
- column[0] = x
-
- for y, lastDiag := 1, x-1; y <= len(r1); y++ {
- oldDiag := column[y]
- cost := 0
- if r1[y-1] != r2[x-1] {
- cost = 1
- }
- column[y] = min(column[y]+1, column[y-1]+1, lastDiag+cost)
- lastDiag = oldDiag
- }
- }
-
- return column[len(r1)]
-}
-
-func min(a, b, c int) int {
- if a < b && a < c {
- return a
- } else if b < c {
- return b
- }
- return c
-}