SimMetrics: misurare la similarità tra stringhe in Java

In questo post vedremo una libreria Open Source Java che ci permette di misurare la similarità tra due stringhe utilizzando diverse metriche di misura, denominata Simmetrics. Questa è stata sviluppata da Sam Chapman dell’Universita di Sheffield e rilasciata secondo la licenza GNU GPL.

Le metriche definite comprendono:

• Levenshtein distance,
• Block distance or city block distance or L2 distance,
• Cosine similarity,
• Jaccard index,
• Needleman–Wunsch algorithm or Sellers algorithm,
• Smith–Waterman algorithm,
• Gotoh distance or Smith-Waterman-Gotoh distance,
• Monge Elkan distance,
• Jaro–Winkler distance,
• Soundex,
• Matching coefficient,
• Dice’s coefficient,
• Jaccard similarity or Jaccard coefficient or Tanimoto coefficient,
• Overlap coefficient,
• Euclidean distance,
• Q-gram distance,
• e altre…

La misura di similarità fornita in output è in formato floating point compreso tra 0.0 e 1.0 ma è anche possibile ottenere una misura non normalizzata.

E’ possibile scaricare la libreria all’indirizzo:

http://sourceforge.net/projects/simmetrics/

L’utilizzo della libreria è molto semplice ed intuitivo; basta instanziare la Classe che rappresenta la misura che vogliamo utilizzare (ad esempio Levenshtein) e poi richiamare il metodo getSimilarity() passando come argomento le due stringhe:

String str1 = "www.appuntisoftware.it";
String str2 = "appuntisoftware";
AbstractStringMetric metric = new Levenshtein();
//oppure
// AbstractStringMetric metric = new CosineSimilarity();
// AbstractStringMetric metric = new EuclideanDistance();
float result = metric.getSimilarity(str1, str2);
System.out.println("La metrica " + metric.getShortDescriptionString() +
 " utilizzata sulle stringhe "" + str1 + "" e "" + str2 + "" restituisce uno score di " + result);

se volessimo invece ottenere il valore non normalizzato della misura utilizziamo questo metodo:

float result = metric.getUnNormalisedSimilarity(str1, str2);

Possiamo elencare tutte le misure definite nella libreria richiamando il metodo statico GetMetricsAvailable() della Classe MetricHandler:

ArrayList<String> metricStrings = MetricHandler.GetMetricsAvailable();

Per poter utilizzare questa classe bisogna però includere nel nostro classpath la libreria JUnit, per il download bisogna andare all’indirizzo https://github.com/KentBeck/junit/downloads. Vediamo ora come poter chiamare tutte le metriche definite nella libreria ed effettuare una misura di similarità con ognuna di esse:

final ArrayList<AbstractStringMetric> testMetricArrayList = new ArrayList<AbstractStringMetric>();
ArrayList<String> metricStrings = MetricHandler.GetMetricsAvailable();
 for(String metricString : metricStrings) {
  System.out.println(metricString);
  testMetricArrayList.add(MetricHandler.createMetric(metricString));
 }
final DecimalFormat df = new DecimalFormat("0.00");
for (int i = 0; i < testMetricArrayList.size(); i++) {
  AbstractStringMetric metric = testMetricArrayList.get(i);
  float result = metric.getSimilarity(str1, str2);
  System.out.print("(" + metric.metgetShortDescriptionString() + ")t");
  System.out.print(df.format(result)+"n");
 }

Questa volta per creare una AbstractStringMetric (una metrica di misura) abbiamo utilizzato il metodo createMetric() che utilizza la tecnica della Reflection (Java Reflection) per instanziare una classe dato il suo nome, aggiungiamo poi tutte le metriche ad un array ed infine le eseguiamo una alla volta all’interno di un altro ciclo for.