Home Show me the Code Cálculo da Distância Levenshtein em Go

Cálculo da Distância Levenshtein em Go

0
0
418

Definição da Distância Levenshtein extraída da Wikipédia:

“Em teoria da informação, a distância Levenshtein ou distância de edição entre dois “strings” (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar um string no outro. Entendemos por “operações” a inserção, deleção ou substituição de um carácter. O nome advém do cientista russo Vladimir Levenshtein, que considerou esta distância já em 1965. É muito útil para aplicações que precisam determinar quão semelhantes dois strings são, como é por exemplo o caso com os verificadores ortográficos.”

Por exemplo, a distância Levenshtein entre Asheville” e “Arizona” é 8.

Segue uma implementação em Go:

package main
import "fmt"
func levenshtein(str1, str2 []rune) int {
s1len := len(str1)
s2len := len(str2)
column := make([]int, len(str1)+1)
for y := 1; y <= s1len; y++ {
column[y] = y
}
for x := 1; x <= s2len; x++ {
column[0] = x
lastkey := x - 1
for y := 1; y <= s1len; y++ {
oldkey := column[y]
var incr int
if str1[y-1] != str2[x-1] {
incr = 1
}
column[y] = minimum(column[y]+1, column[y-1]+1, lastkey+incr)
lastkey = oldkey
}
}
return column[s1len]
}
func minimum(a, b, c int) int {
if a < b {
if a < c {
return a
}
} else {
if b < c {
return b
}
}
return c
}
func main(){
var str1 = []rune("Asheville")
var str2 = []rune("Arizona")
fmt.Println("Distance between Asheville and Arizona:",levenshtein(str1,str2))
str1 = []rune("Python")
str2 = []rune("Peithen")
fmt.Println("Distance between Python and Peithen:",levenshtein(str1,str2))
str1 = []rune("Orange")
str2 = []rune("Apple")
fmt.Println("Distance between Orange and Apple:",levenshtein(str1,str2))
}

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Veja Também

Validação de CPF e CNPJ em Go

Simples e direto. Funções para validar CPF e CNPJ em Go. …