From 20d845cba2858a306fbf8193f510d6da6d2d6fc2 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Wed, 15 Nov 2017 23:56:55 +0100 Subject: Initial import --- LICENSE | 13 +++++++++++++ distance.go | 40 ++++++++++++++++++++++++++++++++++++++++ distance_test.go | 28 ++++++++++++++++++++++++++++ 3 files changed, 81 insertions(+) create mode 100644 LICENSE create mode 100644 distance.go create mode 100644 distance_test.go diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..9863fd4 --- /dev/null +++ b/LICENSE @@ -0,0 +1,13 @@ +Copyright (c) 2017 Dimitri Sokolyuk + +Permission to use, copy, modify, and distribute this software for any +purpose with or without fee is hereby granted, provided that the above +copyright notice and this permission notice appear in all copies. + +THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES +WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR +ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES +WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN +ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF +OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. diff --git a/distance.go b/distance.go new file mode 100644 index 0000000..c6d0959 --- /dev/null +++ b/distance.go @@ -0,0 +1,40 @@ +package lavenshtein + +func Distance(s, t string) int { + a, b := []rune(s), []rune(t) + u, v := vectors(len(b)) + for i, A := range a { + v[0] = i + 1 + for j, B := range b { + v[j+1] = min3(v[j]+1, u[j+1]+1, u[j]+cost(A, B)) + } + u, v = v, u + } + return u[len(u)-1] +} + +func cost(a, b rune) int { + if a != b { + return 1 + } + return 0 +} + +func vectors(n int) ([]int, []int) { + u, v := make([]int, n+1), make([]int, n+1) + for i := 0; i <= n; i++ { + u[i] = i + } + return u, v +} + +func min3(u, v, w int) int { + return min(u, min(v, w)) +} + +func min(u, v int) int { + if u < v { + return u + } + return v +} diff --git a/distance_test.go b/distance_test.go new file mode 100644 index 0000000..50810fa --- /dev/null +++ b/distance_test.go @@ -0,0 +1,28 @@ +package lavenshtein + +import "testing" + +func TestDistance(t *testing.T) { + testCases := []struct { + a, b string + dist int + }{ + {"", "", 0}, + {"aa", "aa", 0}, + {"aa", "ab", 1}, + {"aa", "ba", 1}, + {"aa", "bb", 2}, + {"aa", "", 2}, + {"", "bb", 2}, + {"test", "Test", 1}, + {"тест", "Тест", 1}, + } + for _, tc := range testCases { + t.Run(tc.a+" "+tc.b, func(t *testing.T) { + dist := Distance(tc.a, tc.b) + if dist != tc.dist { + t.Errorf("got %v, want %v", dist, tc.dist) + } + }) + } +} -- cgit v1.2.3