diff options
Diffstat (limited to 'vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go')
-rw-r--r-- | vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go | 43 |
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 -} |