wagner-fischer.go 887 Bytes
Newer Older
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]
}