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

Cálculo da Distância Levenshtein em Go

0
0
865

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

Um guia de boas práticas de segurança para desenvolvimento em Go

Confira este livro on-line gratuito sobre boas práticas de segurança de desenvolvimento pa…