summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2017-11-15 23:56:55 +0100
committerDimitri Sokolyuk <demon@dim13.org>2017-11-15 23:56:55 +0100
commit20d845cba2858a306fbf8193f510d6da6d2d6fc2 (patch)
tree198f39156ba167a8fe15fbda844b159c5a8dee03
Initial import
-rw-r--r--LICENSE13
-rw-r--r--distance.go40
-rw-r--r--distance_test.go28
3 files changed, 81 insertions, 0 deletions
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 <demon@dim13.org>
+
+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)
+ }
+ })
+ }
+}