java - online - Puntuación de similitud-Levenshtein

levenshtein distance online

Question

Implementé el algoritmo Levenshtein en Java y ahora estoy recibiendo las correcciones hechas por el algoritmo, también conocido como el costo. Esto ayuda un poco, pero no mucho, ya que quiero los resultados como un porcentaje.

Así que quiero saber cómo calcular esos puntos de similitud.

También me gustaría saber cómo lo hacen ustedes y por qué.

Answer 1

La distancia de Levenshtein entre dos cadenas se define como el número mínimo de ediciones necesarias para transformar una cadena en otra, con las operaciones de edición permitidas que son la inserción, eliminación o sustitución de un solo carácter. (Wikipedia)

• Así que una distancia Levenshtein de 0 significa que ambas cadenas son iguales.
• La distancia máxima de Levenshtein (todos los caracteres son diferentes) es max (string1.length, string2.length)

Entonces, si necesita un porcentaje, debe usarlo para escalar puntos. Por ejemplo:

"Hola", "Hola" -> Levenstein distancia 1 La distancia máxima de Levenstein para estas dos cadenas es: 5. Entonces, el 20% de los caracteres no coinciden.

String s1 = "Hallo";
String s2 = "Hello";
int lfd = calculateLevensteinDistance(s1, s2);
double ratio = ((double) lfd) / (Math.max(s1.length, s2.length));

Answer 2

Creo que sería útil enlazar LevenshteinDistance

Puede ser utilizado a través de la dependencia maven.

dependencia maven

Creo que es mejor usar esta implementación que escribir su propio código.

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-text</artifactId>
    <version>1.3</version>
</dependency>

Como ejemplo, mira el código de abajo.

import org.apache.commons.text.similarity.LevenshteinDistance;

public class MetricUtils {
    private static LevenshteinDistance lv = new LevenshteinDistance();

    public static void main(String[] args) {
        String s = "running";
        String s1 = "runninh";
        System.out.println(levensteinRatio(s, s1));
    }

    public static double levensteinRatio(String s, String s1) {
        return 1 - ((double) lv.apply(s, s1)) / Math.max(s.length(), s1.length());
    }
}

Answer 3

El valor máximo de la diferencia Levenshtein entre dos cadenas sería el máximo de la longitud de las dos cadenas. (Eso corresponde a un cambio de símbolo para cada uno de los caracteres hasta la longitud de la cadena más corta, más las inserciones o eliminaciones, dependiendo de si va de más corto a más largo o viceversa.) Dado lo anterior, la similitud de los dos Las cuerdas deben ser la relación entre ese máximo y la diferencia entre ese máximo y la diferencia real de Levenshtein.

Las implementaciones del algoritmo de Levenshtein tienden a no registrar cuáles deberían ser esas ediciones, pero no debería ser tan difícil de calcular dado el algoritmo abstracto en la página de Wikipedia .

Answer 4

Para calcular el puntaje, necesita el máximo costo posible (insertar + soltar + sustituir). Luego use la siguiente fórmula:

score = 1 - actual_cost/max_possible_cost

Ver esto para referencia - Levenshtein Score Calculation Func.

Answer 5

Puede descargar StringUtils de Apache Commons e investigar (y quizás usar) su implementación del algoritmo de distancia Levenshtein.

Answer 6

 // Refer This: 100% working

public class demo 
{
public static void main(String[] args) 
{
    String str1, str2;

    str1="12345";
    str2="122345";


    int re=pecentageOfTextMatch(str1, str2);
    System.out.println("Matching Percent"+re);
}

public static int pecentageOfTextMatch(String s0, String s1) 
{                       // Trim and remove duplicate spaces
    int percentage = 0;
    s0 = s0.trim().replaceAll("//s+", " ");
    s1 = s1.trim().replaceAll("//s+", " ");
    percentage=(int) (100 - (float) LevenshteinDistance(s0, s1) * 100 / (float) (s0.length() + s1.length()));
    return percentage;
}

public static int LevenshteinDistance(String s0, String s1) {

    int len0 = s0.length() + 1;
    int len1 = s1.length() + 1;  
    // the array of distances
    int[] cost = new int[len0];
    int[] newcost = new int[len0];

    // initial cost of skipping prefix in String s0
    for (int i = 0; i < len0; i++)
        cost[i] = i;

    // dynamically computing the array of distances

    // transformation cost for each letter in s1
    for (int j = 1; j < len1; j++) {

        // initial cost of skipping prefix in String s1
        newcost[0] = j - 1;

        // transformation cost for each letter in s0
        for (int i = 1; i < len0; i++) {

            // matching current letters in both strings
            int match = (s0.charAt(i - 1) == s1.charAt(j - 1)) ? 0 : 1;

            // computing cost for each transformation
            int cost_replace = cost[i - 1] + match;
            int cost_insert = cost[i] + 1;
            int cost_delete = newcost[i - 1] + 1;

            // keep minimum cost
            newcost[i] = Math.min(Math.min(cost_insert, cost_delete),
                    cost_replace);
        }

        // swap cost/newcost arrays
        int[] swap = cost;
        cost = newcost;
        newcost = swap;
    }

    // the distance is the cost for transforming all letters in both strings
    return cost[len0 - 1];
}

}