wagner-fischer.go

Documentation: github.com/xrash/smetrics

     1  package smetrics
     2  
     3  // The Wagner-Fischer algorithm for calculating the Levenshtein distance.
     4  // The first two parameters are the two strings to be compared. The last three parameters are the insertion cost, the deletion cost and the substitution cost. These are normally defined as 1, 1 and 2 respectively.
     5  func WagnerFischer(a, b string, icost, dcost, scost int) int {
     6  
     7  	// Allocate both rows.
     8  	row1 := make([]int, len(b)+1)
     9  	row2 := make([]int, len(b)+1)
    10  	var tmp []int
    11  
    12  	// Initialize the first row.
    13  	for i := 1; i <= len(b); i++ {
    14  		row1[i] = i * icost
    15  	}
    16  
    17  	// For each row...
    18  	for i := 1; i <= len(a); i++ {
    19  		row2[0] = i * dcost
    20  
    21  		// For each column...
    22  		for j := 1; j <= len(b); j++ {
    23  			if a[i-1] == b[j-1] {
    24  				row2[j] = row1[j-1]
    25  			} else {
    26  				ins := row2[j-1] + icost
    27  				del := row1[j] + dcost
    28  				sub := row1[j-1] + scost
    29  
    30  				if ins < del && ins < sub {
    31  					row2[j] = ins
    32  				} else if del < sub {
    33  					row2[j] = del
    34  				} else {
    35  					row2[j] = sub
    36  				}
    37  			}
    38  		}
    39  
    40  		// Swap the rows at the end of each row.
    41  		tmp = row1
    42  		row1 = row2
    43  		row2 = tmp
    44  	}
    45  
    46  	// Because we swapped the rows, the final result is in row1 instead of row2.
    47  	return row1[len(row1)-1]
    48  }
    49
View as plain text