Bugfix: init values in matrix depend on cost
The first row/column of the Levenshtein matrix must contain the column/row
indexes *multiplied by insertion/deletion cost*. This last part had been
forgotten, working fine in the common case when insertion and deletion cost are
1 but breaking otherwise.
Fixes #12.
diff --git a/levenshtein/levenshtein.go b/levenshtein/levenshtein.go
index e72b09d..45722c2 100644
--- a/levenshtein/levenshtein.go
+++ b/levenshtein/levenshtein.go
@@ -85,13 +85,14 @@
matrix := make([][]int, 2)
// Initialize trivial distances (from/to empty string). That is, fill
- // the left column and the top row with row/column indices.
+ // the left column and the top row with row/column indices multiplied
+ // by deletion/insertion cost.
for i := 0; i < 2; i++ {
matrix[i] = make([]int, width)
- matrix[i][0] = i
+ matrix[i][0] = i * op.DelCost
}
for j := 1; j < width; j++ {
- matrix[0][j] = j
+ matrix[0][j] = j * op.InsCost
}
// Fill in the remaining cells: for each prefix pair, choose the
@@ -99,7 +100,7 @@
for i := 1; i < height; i++ {
cur := matrix[i%2]
prev := matrix[(i-1)%2]
- cur[0] = i
+ cur[0] = i * op.DelCost
for j := 1; j < width; j++ {
delCost := prev[j] + op.DelCost
matchSubCost := prev[j-1]
@@ -160,13 +161,14 @@
matrix := make([][]int, height)
// Initialize trivial distances (from/to empty string). That is, fill
- // the left column and the top row with row/column indices.
+ // the left column and the top row with row/column indices multiplied
+ // by deletion/insertion cost.
for i := 0; i < height; i++ {
matrix[i] = make([]int, width)
- matrix[i][0] = i
+ matrix[i][0] = i * op.DelCost
}
for j := 1; j < width; j++ {
- matrix[0][j] = j
+ matrix[0][j] = j * op.InsCost
}
// Fill in the remaining cells: for each prefix pair, choose the
diff --git a/levenshtein/levenshtein_test.go b/levenshtein/levenshtein_test.go
index 2d2de53..e392e4a 100644
--- a/levenshtein/levenshtein_test.go
+++ b/levenshtein/levenshtein_test.go
@@ -159,6 +159,24 @@
Match,
},
},
+ {
+ source: "me",
+ target: "meme",
+ options: Options{
+ InsCost: 2,
+ DelCost: 1,
+ SubCost: 3,
+ Matches: IdenticalRunes,
+ },
+ distance: 4,
+ ratio: 0.3333333333333333,
+ script: EditScript{
+ Match,
+ Match,
+ Ins,
+ Ins,
+ },
+ },
}
func TestDistanceForStrings(t *testing.T) {
