1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
package smetrics
func WagnerFischer(a, b string, icost, dcost, scost int) int {
// Allocate both rows.
row1 := make([]int, len(b)+1)
row2 := make([]int, len(b)+1)
var tmp []int
// Initialize the first row.
for i := 1; i <= len(b); i++ {
row1[i] = i * icost
}
// For each row...
for i := 1; i <= len(a); i++ {
row2[0] = i * dcost
// For each column...
for j := 1; j <= len(b); j++ {
if a[i-1] == b[j-1] {
row2[j] = row1[j-1]
} else {
ins := row2[j-1] + icost
del := row1[j] + dcost
sub := row1[j-1] + scost
if ins < del && ins < sub {
row2[j] = ins
} else if del < sub {
row2[j] = del
} else {
row2[j] = sub
}
}
}
// Swap the rows at the end of each row.
tmp = row1
row1 = row2
row2 = tmp
}
// Because we swapped the rows, the final result is in row1 instead of row2.
return row1[len(row1)-1]
}
|