Question Score de similarité - Levenshtein


J'ai implémenté l'algorithme Levenshtein en Java et j'obtiens maintenant les corrections apportées par l'algorithme, à savoir le coût. Cela aide un peu mais pas beaucoup puisque je veux les résultats en pourcentage.

Je veux donc savoir comment calculer ces points de similarité.

J'aimerais aussi savoir comment vous le faites et pourquoi.


16
2018-05-22 10:16


origine


Réponses:


le Levenshtein la distance entre deux chaînes est définie comme le nombre minimum de modifications nécessaires pour transformer une chaîne en une autre, les opérations d'édition autorisées étant l'insertion, la suppression ou la substitution d'un seul caractère. (Wikipédia)

  • Donc, une distance Levenshtein de 0 signifie: les deux chaînes sont égales
  • La distance maximale de Levenshtein (tous les caractères sont différents) est max (string1.length, string2.length)

Donc, si vous avez besoin d'un pourcentage, vous devez l'utiliser pour mettre en évidence. Par exemple:

"Bonjour", "bonjour" -> distance levenstein 1 La distance de Max Levenstein pour ces deux cordes est de: 5. Donc, les 20% des personnages ne correspondent pas.

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

25
2018-05-22 12:47



Vous pouvez télécharger Apache Commons StringUtils et étudier (et peut-être utiliser) leur implémentation de l'algorithme de distance de Levenshtein.


16
2018-05-22 11:35



 // 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];
}

}

2
2017-10-08 06:50



La valeur maximale de la différence Levenshtein entre deux chaînes correspondrait au maximum de la longueur des deux chaînes. (Cela correspond à un changement de symbole pour chacun des caractères jusqu’à la longueur de la chaîne plus courte, plus des insertions ou des suppressions selon que vous allez de plus court à plus long ou vice versa.) Compte tenu de cela, la similitude des deux les chaînes doivent être le rapport entre ce maximum et la différence entre ce maximum et la différence réelle de Levenshtein.

Les implémentations de l'algorithme de Levenshtein ont tendance à ne pas enregistrer ce que ces modifications devraient être, mais cela ne devrait pas être si difficile à calculer étant donné l'algorithme abstrait du Page Wikipedia.


0
2018-05-22 12:05



Je pense que ce serait un lien utile LevenshteinDistance

Il peut être utilisé grâce à la dépendance Maven

dépendance Maven

Je pense qu'il est préférable d'utiliser cette implémentation que d'écrire votre propre code.

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

Comme exemple, regardez le code ci-dessous

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());
    }
}

0
2018-04-04 09:47