Score de similarité - Levenshtein

J'ai implémenté l'algorithme de Levenshtein en Java et je suis maintenant obtenir les corrections apportées par l'algorithme, une.k.un. le coût. Cela aide un peu mais pas beaucoup, car je veux les résultats sous forme de pourcentage.

Donc je veux savoir comment calculer ces points de similitude.

Je voudrais aussi savoir comment vous les gens le font et pourquoi.

source d'informationauteur N00programmer

  1. 25

    La Levenshtein distance entre deux chaînes de caractères est défini comme le nombre minimum de modifications qui sont nécessaires pour transformer une chaîne à l'autre, avec à la limite permise de modifier les opérations d'insertion, la suppression ou la substitution d'un seul caractère. (Wikipédia)

    • Donc un Levenshtein de 0 signifie: les deux chaînes sont égales
    • Le maximum de Levenshtein (tous les caractères sont différents) max(chaîne1.longueur, chaîne2.la longueur)

    Donc, si vous avez besoin d'un pourcentage, vous avez de l'utiliser pour les points à l'échelle. Par exemple:

    "Bonjour", "Bonjour" -> distance de Levenstein 1
    Max Levenstein distance de ces deux chaînes est: 5.
    Le 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));
  2. 16

    Vous pouvez télécharger Apache Commons StringUtils et étudier (et peut-être utiliser) leur mise en œuvre de l'algorithme de Levenshtein.

  3. 2
     //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];
}
}
  4. 0

    La valeur maximale de Levenshtein différence entre deux chaînes de caractères serait le maximum de la longueur des deux chaînes. (Qui correspond à un changement de symbole pour chacun des personnages jusqu'à la longueur de la chaîne plus courte, plus des insertions ou des suppressions en fonction de si vous allez du plus court au plus long, ou vice versa.) Étant donné que, de la similitude des deux chaînes doit être le rapport entre le maximum et la différence entre le maximum et le nombre réel de Levenshtein différence.

    Implémentations de l'algorithme de Levenshtein, ont tendance à ne pas enregistrer ce que ces modifications devraient être, mais il ne devrait pas être difficile à calculer, compte tenu de l'algorithme abstrait sur le Page Wikipedia.

  5. 0

    Je pense qu'il serait utile de lien
    LevenshteinDistance

    Il peut être utilisé par maven dependency

    maven dependency

    Je pense qu'il est préférable d'utiliser cette mise en œuvre que d'écrire votre propre code.

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

    Comme exemple regarder code soufflet 

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