mirror of
https://codeberg.org/scip/tablizer.git
synced 2025-12-17 20:41:03 +01:00
46 lines
1.0 KiB
Go
46 lines
1.0 KiB
Go
package fuzzy
|
|
|
|
// LevenshteinDistance measures the difference between two strings.
|
|
// The Levenshtein distance between two words is the minimum number of
|
|
// single-character edits (i.e. insertions, deletions or substitutions)
|
|
// required to change one word into the other.
|
|
//
|
|
// This implemention is optimized to use O(min(m,n)) space and is based on the
|
|
// optimized C version found here:
|
|
// http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#C
|
|
func LevenshteinDistance(s, t string) int {
|
|
r1, r2 := []rune(s), []rune(t)
|
|
column := make([]int, 1, 64)
|
|
|
|
for y := 1; y <= len(r1); y++ {
|
|
column = append(column, y)
|
|
}
|
|
|
|
for x := 1; x <= len(r2); x++ {
|
|
column[0] = x
|
|
|
|
for y, lastDiag := 1, x-1; y <= len(r1); y++ {
|
|
oldDiag := column[y]
|
|
cost := 0
|
|
if r1[y-1] != r2[x-1] {
|
|
cost = 1
|
|
}
|
|
column[y] = min(column[y]+1, column[y-1]+1, lastDiag+cost)
|
|
lastDiag = oldDiag
|
|
}
|
|
}
|
|
|
|
return column[len(r1)]
|
|
}
|
|
|
|
func min2(a, b int) int {
|
|
if a < b {
|
|
return a
|
|
}
|
|
return b
|
|
}
|
|
|
|
func min(a, b, c int) int {
|
|
return min2(min2(a, b), c)
|
|
}
|