summaryrefslogtreecommitdiff
path: root/distance.go
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 /distance.go
Initial import
Diffstat (limited to 'distance.go')
-rw-r--r--distance.go40
1 files changed, 40 insertions, 0 deletions
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
+}