Реализации алгоритмов/Расстояние Левенштейна: различия между версиями
Содержимое удалено Содержимое добавлено
Добавлена реализация на языке Go Метка: визуальный редактор отключён |
|||
Строка 727:
exec @retval = LevenshteinDistance 'Петрова Дарья Ивановна', 'Петрова Марья Ивановна'
select @retval
</source>
== [[w:Go|Go]] ==
<source lang="go">
func distance(s1, s2 string) int {
min := func(values ...int) int {
m := values[0]
for _, v := range values {
if v < m {
m = v
}
}
return m
}
n, m := len(s1), len(s2)
if n > m {
s1, s2 = s2, s1
n, m = m, n
}
currentRow := make([]int, n+1)
previousRow := make([]int, n+1)
for i := range currentRow {
currentRow[i] = i
}
for i := 1; i <= m; i++ {
for j := range currentRow {
previousRow[j] = currentRow[j]
if j == 0 {
currentRow[j] = i
continue
} else {
currentRow[j] = 0
}
add, del, change := previousRow[j]+1, currentRow[j-1]+1, previousRow[j-1]
if s1[j-1] != s2[i-1] {
change++
}
currentRow[j] = min(add, del, change)
}
}
return currentRow[n]
}
</source>
| |||