Comparazione delle stringhe di similarità in Java

Voglio confrontare più stringhe tra loro e trovare quelle che sono le più simili. Mi stavo chiedendo se c’è qualche libreria, metodo o procedura migliore che mi restituire quali stringhe sono più simili ad altre stringhe. Per esempio:

  • “La volpe veloce saltò” -> “La volpe sobbalzò”
  • “La volpe veloce saltò” -> “La volpe”

Questo confronto restituirebbe che il primo è più simile del secondo.

Credo di aver bisogno di un metodo come:

double similarityIndex(String s1, String s2) 

C’è una cosa del genere da qualche parte?

EDIT: Perché sto facendo questo? Sto scrivendo uno script che confronta l’output di un file MS Project con l’output di un sistema legacy che gestisce le attività. Poiché il sistema legacy ha una larghezza di campo molto limitata, quando i valori vengono aggiunti le descrizioni sono abbreviate. Voglio un modo semi-automatico per trovare quali voci da MS Project sono simili alle voci sul sistema in modo da poter ottenere le chiavi generate. Ha degli svantaggi, in quanto deve essere ancora controllato manualmente, ma farebbe risparmiare un sacco di lavoro

    Sì, ci sono molti algoritmi ben documentati come:

    • Somiglianza del coseno
    • Somiglianza Jaccard
    • Coefficiente dei dadi
    • Somiglianza corrispondente
    • Sovrapposizione di somiglianza
    • ecc ecc

    In alternativa puoi controllare questo

    Controlla anche questi progetti:

    Il modo comune di calcolare la similarità tra due stringhe in una moda dallo 0% al 100% , come usato in molte librerie, è misurare quanto (in%) si dovrebbe cambiare la stringa più lunga per trasformarla in una più breve:

     /** * Calculates the similarity (a number within 0 and 1) between two strings. */ public static double similarity(String s1, String s2) { String longer = s1, shorter = s2; if (s1.length() < s2.length()) { // longer should always have greater length longer = s2; shorter = s1; } int longerLength = longer.length(); if (longerLength == 0) { return 1.0; /* both strings are zero length */ } return (longerLength - editDistance(longer, shorter)) / (double) longerLength; } // you can use StringUtils.getLevenshteinDistance() as the editDistance() function // full copy-paste working code is below 

    Calcolo di editDistance() :

    La funzione editDistance() sopra è prevista per calcolare la distanza di modifica tra le due stringhe. Esistono diverse implementazioni in questo passaggio, ognuna delle quali può soddisfare meglio uno scenario specifico. Il più comune è l' algoritmo di distanza di Levenshtein e lo utilizzeremo nel nostro esempio di seguito (per stringhe molto grandi, altri algoritmi sono probabilmente in grado di funzionare meglio).

    Ecco due opzioni per calcolare la distanza di modifica:

    • È ansible utilizzare l'implementazione di Apache Commons Text della distanza di Levenshtein: apply(CharSequence left, CharSequence rightt)
    • Implementalo nel tuo. Di seguito troverai un'implementazione di esempio.

    Esempio di lavoro:

    Guarda la demo online qui.

     public class StringSimilarity { /** * Calculates the similarity (a number within 0 and 1) between two strings. */ public static double similarity(String s1, String s2) { String longer = s1, shorter = s2; if (s1.length() < s2.length()) { // longer should always have greater length longer = s2; shorter = s1; } int longerLength = longer.length(); if (longerLength == 0) { return 1.0; /* both strings are zero length */ } /* // If you have Apache Commons Text, you can use it to calculate the edit distance: LevenshteinDistance levenshteinDistance = new LevenshteinDistance(); return (longerLength - levenshteinDistance.apply(longer, shorter)) / (double) longerLength; */ return (longerLength - editDistance(longer, shorter)) / (double) longerLength; } // Example implementation of the Levenshtein Edit Distance // See http://rosettacode.org/wiki/Levenshtein_distance#Java public static int editDistance(String s1, String s2) { s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); int[] costs = new int[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { int lastValue = i; for (int j = 0; j <= s2.length(); j++) { if (i == 0) costs[j] = j; else { if (j > 0) { int newValue = costs[j - 1]; if (s1.charAt(i - 1) != s2.charAt(j - 1)) newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1; costs[j - 1] = lastValue; lastValue = newValue; } } } if (i > 0) costs[s2.length()] = lastValue; } return costs[s2.length()]; } public static void printSimilarity(String s, String t) { System.out.println(String.format( "%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t)); } public static void main(String[] args) { printSimilarity("", ""); printSimilarity("1234567890", "1"); printSimilarity("1234567890", "123"); printSimilarity("1234567890", "1234567"); printSimilarity("1234567890", "1234567890"); printSimilarity("1234567890", "1234567980"); printSimilarity("47/2010", "472010"); printSimilarity("47/2010", "472011"); printSimilarity("47/2010", "AB.CDEF"); printSimilarity("47/2010", "4B.CDEFG"); printSimilarity("47/2010", "AB.CDEFG"); printSimilarity("The quick fox jumped", "The fox jumped"); printSimilarity("The quick fox jumped", "The fox"); printSimilarity("kitten", "sitting"); } } 

    Produzione:

     1.000 is the similarity between "" and "" 0.100 is the similarity between "1234567890" and "1" 0.300 is the similarity between "1234567890" and "123" 0.700 is the similarity between "1234567890" and "1234567" 1.000 is the similarity between "1234567890" and "1234567890" 0.800 is the similarity between "1234567890" and "1234567980" 0.857 is the similarity between "47/2010" and "472010" 0.714 is the similarity between "47/2010" and "472011" 0.000 is the similarity between "47/2010" and "AB.CDEF" 0.125 is the similarity between "47/2010" and "4B.CDEFG" 0.000 is the similarity between "47/2010" and "AB.CDEFG" 0.700 is the similarity between "The quick fox jumped" and "The fox jumped" 0.350 is the similarity between "The quick fox jumped" and "The fox" 0.571 is the similarity between "kitten" and "sitting" 

    Ho tradotto l’ algoritmo della distanza di Levenshtein in JavaScript:

     String.prototype.LevenshteinDistance = function (s2) { var array = new Array(this.length + 1); for (var i = 0; i < this.length + 1; i++) array[i] = new Array(s2.length + 1); for (var i = 0; i < this.length + 1; i++) array[i][0] = i; for (var j = 0; j < s2.length + 1; j++) array[0][j] = j; for (var i = 1; i < this.length + 1; i++) { for (var j = 1; j < s2.length + 1; j++) { if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1]; else { array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1); array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1); } } } return array[this.length][s2.length]; }; 

    È ansible utilizzare la distanza di Levenshtein per calcolare la differenza tra due stringhe. http://en.wikipedia.org/wiki/Levenshtein_distance

    Ci sono davvero un sacco di misure di similarità delle stringhe là fuori:

    • Levenshtein modifica la distanza;
    • Distanza Damerau-Levenshtein;
    • Somiglianza Jaro-Winkler;
    • La più lunga distanza di modifica successiva in comune;
    • Q-Gram (Ukkonen);
    • distanza n-gram (Kondrak);
    • Indice Jaccard;
    • Coefficiente di Sorensen-Dice;
    • Somiglianza del coseno;

    Puoi trovare spiegazioni e l’implementazione java di questi qui: https://github.com/tdebatty/java-string-similarity

    È ansible ottenere questo utilizzando la libreria java apache commons . Dai uno sguardo a queste due funzioni al suo interno:
    – getLevenshteinDistance
    – getFuzzyDistance

    In teoria, puoi confrontare le distanze di modifica .

    Questo è tipicamente fatto usando una misura di distanza di modifica . La ricerca di “modifica distanza java” genera un numero di librerie, come questa .

    Mi sembra un cercatore di plagio se la tua stringa si trasforma in un documento. Forse cercare con quel termine farà apparire qualcosa di buono.

    “Programmare l’intelligenza collettiva” ha un capitolo sul determinare se due documenti sono simili. Il codice è in Python, ma è pulito e facile da portare.

    Grazie al primo rispondente, penso che ci siano 2 calcoli di computeEditDistance (s1, s2). A causa dell’elevato tempo di spesa, ha deciso di migliorare le prestazioni del codice. Così:

     public class LevenshteinDistance { public static int computeEditDistance(String s1, String s2) { s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); int[] costs = new int[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { int lastValue = i; for (int j = 0; j <= s2.length(); j++) { if (i == 0) { costs[j] = j; } else { if (j > 0) { int newValue = costs[j - 1]; if (s1.charAt(i - 1) != s2.charAt(j - 1)) { newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1; } costs[j - 1] = lastValue; lastValue = newValue; } } } if (i > 0) { costs[s2.length()] = lastValue; } } return costs[s2.length()]; } public static void printDistance(String s1, String s2) { double similarityOfStrings = 0.0; int editDistance = 0; if (s1.length() < s2.length()) { // s1 should always be bigger String swap = s1; s1 = s2; s2 = swap; } int bigLen = s1.length(); editDistance = computeEditDistance(s1, s2); if (bigLen == 0) { similarityOfStrings = 1.0; /* both strings are zero length */ } else { similarityOfStrings = (bigLen - editDistance) / (double) bigLen; } ////////////////////////// //System.out.println(s1 + "-->" + s2 + ": " + // editDistance + " (" + similarityOfStrings + ")"); System.out.println(editDistance + " (" + similarityOfStrings + ")"); } public static void main(String[] args) { printDistance("", ""); printDistance("1234567890", "1"); printDistance("1234567890", "12"); printDistance("1234567890", "123"); printDistance("1234567890", "1234"); printDistance("1234567890", "12345"); printDistance("1234567890", "123456"); printDistance("1234567890", "1234567"); printDistance("1234567890", "12345678"); printDistance("1234567890", "123456789"); printDistance("1234567890", "1234567890"); printDistance("1234567890", "1234567980"); printDistance("47/2010", "472010"); printDistance("47/2010", "472011"); printDistance("47/2010", "AB.CDEF"); printDistance("47/2010", "4B.CDEFG"); printDistance("47/2010", "AB.CDEFG"); printDistance("The quick fox jumped", "The fox jumped"); printDistance("The quick fox jumped", "The fox"); printDistance("The quick fox jumped", "The quick fox jumped off the balcany"); printDistance("kitten", "sitting"); printDistance("rosettacode", "raisethysword"); printDistance(new StringBuilder("rosettacode").reverse().toString(), new StringBuilder("raisethysword").reverse().toString()); for (int i = 1; i < args.length; i += 2) { printDistance(args[i - 1], args[i]); } } }