summaryrefslogtreecommitdiff
path: root/internal/levenshtein
diff options
context:
space:
mode:
Diffstat (limited to 'internal/levenshtein')
-rw-r--r--internal/levenshtein/levenshtein.go11
-rw-r--r--internal/levenshtein/levenshtein_test.go300
2 files changed, 158 insertions, 153 deletions
diff --git a/internal/levenshtein/levenshtein.go b/internal/levenshtein/levenshtein.go
index 96995c3..f2405c4 100644
--- a/internal/levenshtein/levenshtein.go
+++ b/internal/levenshtein/levenshtein.go
@@ -1,9 +1,10 @@
package levenshtein
import (
- "unicode/utf8"
- "unicode"
"strings"
+ "unicode"
+ "unicode/utf8"
+
"golang.org/x/text/runes"
"golang.org/x/text/transform"
"golang.org/x/text/unicode/norm"
@@ -36,6 +37,9 @@ func levenshtein(os, ot string) int {
for i := 0; i < n; i++ {
v1[0] = i + 1
for j := 0; j < m; j++ {
+ // calculate deletion cost,
+ // insertion cost and
+ // substitution cost
dc := v0[j+1] + 1
ic := v1[j] + 1
var sc int
@@ -44,6 +48,7 @@ func levenshtein(os, ot string) int {
} else {
sc = v0[j] + 1
}
+ // take the min of all the costs
v1[j+1] = min(min(dc, ic), sc)
}
v0, v1 = v1, v0
@@ -84,7 +89,7 @@ func DiscoveryScore(search string, displays map[string]string, keywords map[stri
// length and nil error is returned
_, _ = catalogKW.WriteString(v)
}
- scoreKW := 3*adjusted(search, catalogKW.String())
+ scoreKW := KeywordPenalty * adjusted(search, catalogKW.String())
// if both scores are positive, return the min
if scoreDN >= 0 && scoreKW >= 0 {
diff --git a/internal/levenshtein/levenshtein_test.go b/internal/levenshtein/levenshtein_test.go
index 41f7f4a..5a1a427 100644
--- a/internal/levenshtein/levenshtein_test.go
+++ b/internal/levenshtein/levenshtein_test.go
@@ -3,163 +3,163 @@ package levenshtein
import "testing"
func TestLevenshtein(t *testing.T) {
- cases := []struct{
- a string
- b string
- score int
- }{
- {
- a: "foo",
- b: "foo",
- score: 0,
- },
- {
- a: "foo",
- b: "foo",
- score: 0,
- },
- {
- a: "foo",
- b: "foosd",
- score: 2,
- },
- {
- a: "foo",
- b: "bla",
- score: 3,
- },
- {
- a: "foo",
- b: "",
- score: 3,
- },
- {
- a: "",
- b: "foo",
- score: 3,
- },
- }
- for i, c := range cases {
- g := levenshtein(c.a, c.b)
- if g != c.score {
- t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
- }
+ cases := []struct {
+ a string
+ b string
+ score int
+ }{
+ {
+ a: "foo",
+ b: "foo",
+ score: 0,
+ },
+ {
+ a: "foo",
+ b: "foo",
+ score: 0,
+ },
+ {
+ a: "foo",
+ b: "foosd",
+ score: 2,
+ },
+ {
+ a: "foo",
+ b: "bla",
+ score: 3,
+ },
+ {
+ a: "foo",
+ b: "",
+ score: 3,
+ },
+ {
+ a: "",
+ b: "foo",
+ score: 3,
+ },
+ }
+ for i, c := range cases {
+ g := levenshtein(c.a, c.b)
+ if g != c.score {
+ t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
}
+ }
}
func TestAdjusted(t *testing.T) {
- cases := []struct{
- a string
- b string
- score int
- }{
- {
- a: "foo",
- b: "foo",
- score: 0,
- },
- {
- a: "foo",
- b: "foo",
- score: 0,
- },
- {
- a: "foo",
- b: "foosd",
- score: 2,
- },
- {
- a: "foo",
- b: "bla",
- score: -1,
- },
- {
- a: "bla foo",
- b: "bla",
- score: -1,
- },
- {
- a: "foo",
- b: "",
- score: -1,
- },
- {
- a: "",
- b: "foo",
- score: 3,
- },
- }
- for i, c := range cases {
- g := adjusted(c.a, c.b)
- if g != c.score {
- t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
- }
+ cases := []struct {
+ a string
+ b string
+ score int
+ }{
+ {
+ a: "foo",
+ b: "foo",
+ score: 0,
+ },
+ {
+ a: "foo",
+ b: "foo",
+ score: 0,
+ },
+ {
+ a: "foo",
+ b: "foosd",
+ score: 2,
+ },
+ {
+ a: "foo",
+ b: "bla",
+ score: -1,
+ },
+ {
+ a: "bla foo",
+ b: "bla",
+ score: -1,
+ },
+ {
+ a: "foo",
+ b: "",
+ score: -1,
+ },
+ {
+ a: "",
+ b: "foo",
+ score: 3,
+ },
+ }
+ for i, c := range cases {
+ g := adjusted(c.a, c.b)
+ if g != c.score {
+ t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
}
+ }
}
func TestDiscoveryScore(t *testing.T) {
- cases := []struct{
- q string
- disp map[string]string
- keys map[string]string
- score int
- }{
- {
- q: "test",
- disp: map[string]string{
- "en": "test",
- "de": "test",
- },
- keys: map[string]string{
- "en": "testing",
- "de": "testing",
- },
- score: 4,
- },
- {
- q: "test",
- disp: map[string]string{
- "en": "testing",
- "de": "testing",
- },
- keys: map[string]string{
- "en": "test",
- "de": "test",
- },
- score: 8,
- },
- {
- q: "foo",
- disp: map[string]string{
- "en": "test",
- "de": "testing",
- },
- keys: map[string]string{
- "en": "foo",
- "de": "foo",
- },
- score: 6,
- },
- {
- q: "fox",
- disp: map[string]string{
- "en": "test",
- "de": "testing",
- },
- keys: map[string]string{
- "en": "foo",
- "de": "foo",
- },
- score: -2,
- },
- }
+ cases := []struct {
+ q string
+ disp map[string]string
+ keys map[string]string
+ score int
+ }{
+ {
+ q: "test",
+ disp: map[string]string{
+ "en": "test",
+ "de": "test",
+ },
+ keys: map[string]string{
+ "en": "testing",
+ "de": "testing",
+ },
+ score: 4,
+ },
+ {
+ q: "test",
+ disp: map[string]string{
+ "en": "testing",
+ "de": "testing",
+ },
+ keys: map[string]string{
+ "en": "test",
+ "de": "test",
+ },
+ score: 8,
+ },
+ {
+ q: "foo",
+ disp: map[string]string{
+ "en": "test",
+ "de": "testing",
+ },
+ keys: map[string]string{
+ "en": "foo",
+ "de": "foo",
+ },
+ score: 6,
+ },
+ {
+ q: "fox",
+ disp: map[string]string{
+ "en": "test",
+ "de": "testing",
+ },
+ keys: map[string]string{
+ "en": "foo",
+ "de": "foo",
+ },
+ score: -2,
+ },
+ }
- for i, c := range cases {
- g := DiscoveryScore(c.q, c.disp, c.keys)
- if g != c.score {
- t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
- }
+ for i, c := range cases {
+ g := DiscoveryScore(c.q, c.disp, c.keys)
+ if g != c.score {
+ t.Fatalf("case %d not equal, got: %d, want: %d", i, g, c.score)
}
+ }
}
func TestRemoveDiacritics(t *testing.T) {
@@ -179,9 +179,9 @@ func TestRemoveDiacritics(t *testing.T) {
e: nil,
},
{
- input: "GÉANT",
- want: "GEANT",
- e: nil,
+ input: "GÉANT",
+ want: "GEANT",
+ e: nil,
},
}