From ff5c1292fe8f08f1334c80580d710a642e508940 Mon Sep 17 00:00:00 2001 From: Tulir Asokan Date: Tue, 22 May 2018 17:28:19 +0300 Subject: Add fuzzysearch to vendor/ --- .../evidlo/fuzzysearch/fuzzy/levenshtein.go | 43 ++++++++++++++++++++++ 1 file changed, 43 insertions(+) create mode 100644 vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go (limited to 'vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go') diff --git a/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go b/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go new file mode 100644 index 0000000..237923d --- /dev/null +++ b/vendor/github.com/evidlo/fuzzysearch/fuzzy/levenshtein.go @@ -0,0 +1,43 @@ +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 +} -- cgit v1.2.3