Instantly share code, notes, and snippets.

# alediaferia/levenshtein_distance.go Last active Jan 9, 2018

What would you like to do?
 // This implementation takes advantage of the 2-columns // approach as shown in // https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows // // You are encouraged to use this function when simply // interested in the levenshtein distance between 2 words. func LevenshteinDistance(source, destination string) int { vec1 := make([]int, len(destination) + 1) vec2 := make([]int, len(destination) + 1) w1 := []rune(source) w2 := []rune(destination) // initializing vec1 for i := 0; i < len(vec1); i++ { vec1[i] = i } // initializing the matrix for i := 0; i < len(w1); i++ { vec2[0] = i + 1; for j := 0; j < len(w2); j++ { cost := 1 if (w1[i] == w2[j]) { cost = 0 } min := minimum(vec2[j] + 1, vec1[j + 1] + 1, vec1[j] + cost) vec2[j + 1] = min } for j := 0; j < len(vec1); j++ { vec1[j] = vec2[j] } } return vec2[len(w2)] }
 // a convenience function for computing the minimum // integer value func minimum(value0 int, values ...int) (int) { min := value0 for _, v := range values { if v < min { min = v } } return min }