java string similarity
v2.0.0
Une bibliothèque implémentant différentes mesures de similarité de chaînes et de distance. Une douzaine d'algorithmes (y compris la distance d'édition et les frères et sœurs de Levenshtein, Jaro-Winkler, la sous-séquence commune la plus longue, la similarité cosinus, etc.) sont actuellement implémentés. Consultez le tableau récapitulatif ci-dessous pour la liste complète...
Utiliser maven :
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
Ou vérifiez les versions.
Cette bibliothèque nécessite Java 8 ou plus récent.
Les principales caractéristiques de chaque algorithme implémenté sont présentées ci-dessous. La colonne "coût" donne une estimation du coût de calcul pour calculer la similarité entre deux chaînes de longueur m et n respectivement.
| Normalisé ? | Métrique? | Taper | Coût | Utilisation typique | ||
|---|---|---|---|---|---|---|
| Levenshtein | distance | Non | Oui | O(m*n) 1 | ||
| Levenshtein normalisé | distance similarité | Oui | Non | O(m*n) 1 | ||
| Levenshtein pondéré | distance | Non | Non | O(m*n) 1 | ROC | |
| Damerau-Levenshtein 3 | distance | Non | Oui | O(m*n) 1 | ||
| Alignement optimal des cordes 3 | distance | Non | Non | O(m*n) 1 | ||
| Jaro Winkler | similarité distance | Oui | Non | O(m*n) | correction d'une faute de frappe | |
| Sous-séquence commune la plus longue | distance | Non | Non | O(m*n) 1,2 | utilitaire diff, réconciliation GIT | |
| Sous-séquence commune la plus longue métrique | distance | Oui | Oui | O(m*n) 1,2 | ||
| N-gramme | distance | Oui | Non | O(m*n) | ||
| Q-gramme | distance | Non | Non | Profil | O(m+n) | |
| Similitude cosinus | similarité distance | Oui | Non | Profil | O(m+n) | |
| Index Jaccard | similarité distance | Oui | Oui | Ensemble | O(m+n) | |
| Coefficient de Sorensen-Dice | similarité distance | Oui | Non | Ensemble | O(m+n) | |
| Ratcliff-Obershelp | similarité distance | Oui | Non | ? |
[1] Dans cette bibliothèque, la distance d'édition de Levenshtein, la distance LCS et leurs frères et sœurs sont calculés à l'aide de la méthode de programmation dynamique , qui a un coût O(mn). Pour la distance de Levenshtein, l'algorithme est parfois appelé algorithme de Wagner-Fischer (« The string-to-string correction problem », 1974). L'algorithme original utilise une matrice de taille mxn pour stocker la distance de Levenshtein entre les préfixes de chaîne.
Si l'alphabet est fini, il est possible d'utiliser la méthode de quatre russes (Arlazarov et al. "Sur la construction économique de la fermeture transitive d'un graphe orienté", 1970) pour accélérer le calcul. Ceci a été publié par Masek en 1980 ("A Faster Algorithm Computing String Edit Distances"). Cette méthode divise la matrice en blocs de taille tx t. Chaque bloc possible est précalculé pour produire une table de recherche. Cette table de recherche peut ensuite être utilisée pour calculer la similarité (ou la distance) des chaînes en O (nm/t). Habituellement, t est choisi comme log(m) si m > n. Le coût de calcul qui en résulte est donc O(mn/log(m)). Cette méthode n’a pas (encore) été implémentée.
[2] Dans « Longueur des sous-séquences communes maximales », KS Larsen a proposé un algorithme qui calcule la longueur du LCS dans le temps O(log(m).log(n)). Mais l'algorithme a un besoin en mémoire O(m.n²) et n'a donc pas été implémenté ici.
[3] Il existe deux variantes de la distance entre les cordes Damerau-Levenshtein : Damerau-Levenshtein avec transpositions adjacentes (également parfois appelée distance Damerau-Levenshtein sans restriction) et l'alignement optimal des cordes (également parfois appelé distance d'édition restreinte). Pour l’alignement optimal des chaînes, aucune sous-chaîne ne peut être modifiée plus d’une fois.
Bien que le sujet puisse paraître simple, il existe de nombreux algorithmes différents pour mesurer la similarité ou la distance d’un texte. La bibliothèque définit donc certaines interfaces pour les catégoriser.
Généralement, les algorithmes qui implémentent NormalizedStringSimilarity implémentent également NormalizedStringDistance et similarity = 1 - distance. Mais il y a quelques exceptions, comme la similarité et la distance N-Gram (Kondrak)...
L'interface MetricStringDistance : Certaines distances sont en fait des distances métriques, ce qui signifie qu'il faut vérifier l'inégalité triangulaire d(x, y) <= d(x,z) + d(z,y). Par exemple, Levenshtein est une distance métrique, mais NormalizedLevenshtein ne l'est pas.
De nombreux algorithmes de recherche du plus proche voisin et structures d’indexation reposent sur l’inégalité triangulaire. Vous pouvez consulter "Similarity Search, The Metric Space Approach" de Zezula et al. pour une enquête. Ceux-ci ne peuvent pas être utilisés avec des mesures de similarité non métriques.
Lisez Javadoc pour une description détaillée
Quelques algorithmes fonctionnent en convertissant des chaînes en ensembles de n-grammes (séquences de n caractères, parfois également appelées k-shingles). La similarité ou la distance entre les cordes est alors la similarité ou la distance entre les ensembles.
Certains d'entre eux, comme Jaccard, considèrent les ficelles comme des ensembles de bardeaux, et ne considèrent pas le nombre d'occurrences de chaque bardeau. D'autres, comme la similarité cosinus, fonctionnent en utilisant ce qu'on appelle parfois le profil des cordes, qui prend en compte le nombre d'occurrences de chaque bardeau.
Pour ces algorithmes, un autre cas d’utilisation est possible lorsqu’il s’agit de grands ensembles de données :
La distance de Levenshtein entre deux mots est le nombre minimum de modifications d'un seul caractère (insertions, suppressions ou substitutions) requises pour transformer un mot en un autre.
Il s'agit d'une distance de chaîne métrique. Cette implémentation utilise une programmation dynamique (algorithme de Wagner-Fischer), avec seulement 2 lignes de données. L'encombrement est donc O(m) et l'algorithme s'exécute en O(mn).
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Levenshtein l = new Levenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}Cette distance est calculée comme la distance de Levenshtein divisée par la longueur de la chaîne la plus longue. La valeur résultante est toujours dans l'intervalle [0.0 1.0] mais ce n'est plus une métrique !
La similarité est calculée comme 1 - distance normalisée.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
NormalizedLevenshtein l = new NormalizedLevenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}Une implémentation de Levenshtein qui permet de définir différents poids pour différentes substitutions de caractères.
Cet algorithme est généralement utilisé pour les applications de reconnaissance optique de caractères (OCR). Pour l'OCR, le coût de substitution de P et R est inférieur au coût de substitution de P et M par exemple parce que du point de vue OCR, P est similaire à R.
Il peut également être utilisé pour la correction automatique de la saisie au clavier. Ici le coût de substitution de E et R est moindre par exemple car ceux-ci sont situés l'un à côté de l'autre sur un clavier AZERTY ou QWERTY. Par conséquent, la probabilité que l’utilisateur ait mal saisi les caractères est plus élevée.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
WeightedLevenshtein wl = new WeightedLevenshtein (
new CharacterSubstitutionInterface () {
public double cost ( char c1 , char c2 ) {
// The cost for substituting 't' and 'r' is considered
// smaller as these 2 are located next to each other
// on a keyboard
if ( c1 == 't' && c2 == 'r' ) {
return 0.5 ;
}
// For most cases, the cost of substituting 2 characters
// is 1.0
return 1.0 ;
}
});
System . out . println ( wl . distance ( "String1" , "Srring2" ));
}
}Semblable à Levenshtein, la distance Damerau-Levenshtein avec transposition (appele aussi parfois la distance Damerau-Levenshtein sans restriction) est le nombre minimum d'opérations nécessaires pour transformer une chaîne en une autre, où une opération est définie comme une insertion, une suppression ou une substitution d'un un seul caractère, ou une transposition de deux caractères adjacents .
Elle respecte l'inégalité triangulaire et constitue donc une distance métrique.
Cela ne doit pas être confondu avec la distance d'alignement optimale des chaînes, qui est une extension dans laquelle aucune sous-chaîne ne peut être modifiée plus d'une fois.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Damerau d = new Damerau ();
// 1 substitution
System . out . println ( d . distance ( "ABCDEF" , "ABDCEF" ));
// 2 substitutions
System . out . println ( d . distance ( "ABCDEF" , "BACDFE" ));
// 1 deletion
System . out . println ( d . distance ( "ABCDEF" , "ABCDE" ));
System . out . println ( d . distance ( "ABCDEF" , "BCDEF" ));
System . out . println ( d . distance ( "ABCDEF" , "ABCGDEF" ));
// All different
System . out . println ( d . distance ( "ABCDEF" , "POIU" ));
}
}Produira :
1.0
2.0
1.0
1.0
1.0
6.0
La variante d'alignement optimal des chaînes de Damerau – Levenshtein (parfois appelée distance d'édition restreinte) calcule le nombre d'opérations d'édition nécessaires pour rendre les chaînes égales à condition qu'aucune sous-chaîne ne soit éditée plus d'une fois , alors que le vrai Damerau – Levenshtein ne présente rien de tel. restriction. La différence avec l'algorithme de distance de Levenshtein est l'ajout d'une récurrence pour les opérations de transposition.
Notez que pour la distance d'alignement optimale des chaînes, l'inégalité triangulaire ne tient pas et ce n'est donc pas une vraie métrique.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
OptimalStringAlignment osa = new OptimalStringAlignment ();
System . out . println ( osa . distance ( "CA" , "ABC" ));;
}
}Produira :
3.0
Jaro-Winkler est une distance de vérification des chaînes qui a été développée dans le domaine du couplage d'enregistrements (détection des doublons) (Winkler, 1990). La métrique de distance Jaro-Winkler est conçue et mieux adaptée aux chaînes courtes telles que les noms de personnes et à la détection des fautes de frappe de transposition.
Jaro-Winkler calcule la similarité entre 2 chaînes et la valeur renvoyée se situe dans l'intervalle [0.0, 1.0]. C'est (en gros) une variante de Damerau-Levenshtein, où la transposition de 2 caractères proches est considérée comme moins importante que la transposition de 2 caractères éloignés l'un de l'autre. Jaro-Winkler pénalise les ajouts ou substitutions qui ne peuvent être exprimés comme des transpositions.
La distance est calculée comme suit : 1 - similarité Jaro-Winkler.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
JaroWinkler jw = new JaroWinkler ();
// substitution of s and t
System . out . println ( jw . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( jw . similarity ( "My string" , "My ntrisg" ));
}
}produira :
0.9740740656852722
0.8962963223457336
Le problème de la plus longue sous-séquence commune (LCS) consiste à trouver la plus longue sous-séquence commune à deux (ou plusieurs) séquences. Cela diffère des problèmes de recherche de sous-chaînes communes : contrairement aux sous-chaînes, les sous-séquences ne sont pas obligées d'occuper des positions consécutives dans les séquences d'origine.
Il est utilisé par l'utilitaire diff, par Git pour réconcilier plusieurs modifications, etc.
La distance LCS entre les chaînes X (de longueur n) et Y (de longueur m) est n + m - 2 |LCS(X, Y)| min = 0 max = n + m
La distance LCS est équivalente à la distance de Levenshtein lorsque seules l'insertion et la suppression sont autorisées (pas de substitution), ou lorsque le coût de la substitution est le double du coût d'une insertion ou d'une suppression.
Cette classe implémente l'approche de programmation dynamique, qui a un encombrement O(mn) et un coût de calcul O(mn).
Dans "Length of Maximal Common Subsequences", KS Larsen a proposé un algorithme qui calcule la longueur du LCS dans le temps O(log(m).log(n)). Mais l'algorithme a un besoin en mémoire O(m.n²) et n'a donc pas été implémenté ici.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence ();
// Will produce 4.0
System . out . println ( lcs . distance ( "AGCAT" , "GAC" ));
// Will produce 1.0
System . out . println ( lcs . distance ( "AGCAT" , "AGCT" ));
}
}Métrique de distance basée sur la sous-séquence commune la plus longue, d'après les notes « Une métrique de chaîne basée sur LCS » de Daniel Bakkelund. http://heim.ifi.uio.no/~danielry/StringMetric.pdf
La distance est calculée comme 1 - |LCS(s1, s2)| /max(|s1|, |s2|)
public class MyApp {
public static void main ( String [] args ) {
info . debatty . java . stringsimilarity . MetricLCS lcs =
new info . debatty . java . stringsimilarity . MetricLCS ();
String s1 = "ABCDEFG" ;
String s2 = "ABCDEFHJKL" ;
// LCS: ABCDEF => length = 6
// longest = s2 => length = 10
// => 1 - 6/10 = 0.4
System . out . println ( lcs . distance ( s1 , s2 ));
// LCS: ABDF => length = 4
// longest = ABDEF => length = 5
// => 1 - 4 / 5 = 0.2
System . out . println ( lcs . distance ( "ABDEF" , "ABDIF" ));
}
}Distance N-Gram normalisée telle que définie par Kondrak, "N-Gram Similarity and Distance", String Processing and Information Retrieval, Lecture Notes in Computer Science Volume 3772, 2005, pp 115-126.
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
L'algorithme utilise l'apposition du caractère spécial 'n' pour augmenter le poids des premiers caractères. La normalisation est obtenue en divisant le score de similarité total par la longueur originale du mot le plus long.
Dans l'article, Kondrak définit également une mesure de similarité, qui n'est pas (encore) mise en œuvre.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
// produces 0.583333
NGram twogram = new NGram ( 2 );
System . out . println ( twogram . distance ( "ABCD" , "ABTUIO" ));
// produces 0.97222
String s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp" ;
String s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x" ;
NGram ngram = new NGram ( 4 );
System . out . println ( ngram . distance ( s1 , s2 ));
}
}Quelques algorithmes fonctionnent en convertissant des chaînes en ensembles de n-grammes (séquences de n caractères, parfois également appelées k-shingles). La similarité ou la distance entre les cordes est alors la similarité ou la distance entre les ensembles.
Le coût du calcul de ces similitudes et distances est principalement dominé par le k-shingling (conversion des chaînes en séquences de k caractères). Il existe donc généralement deux cas d’utilisation pour ces algorithmes :
Calculez directement la distance entre les chaînes :
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
QGram dig = new QGram ( 2 );
// AB BC CD CE
// 1 1 1 0
// 1 1 0 1
// Total: 2
System . out . println ( dig . distance ( "ABCD" , "ABCE" ));
}
}Ou, pour les grands ensembles de données, précalculez le profil de toutes les chaînes. La similarité peut alors être calculée entre profils :
import info . debatty . java . stringsimilarity . KShingling ;
import info . debatty . java . stringsimilarity . StringProfile ;
/**
* Example of computing cosine similarity with pre-computed profiles.
*/
public class PrecomputedCosine {
public static void main ( String [] args ) throws Exception {
String s1 = "My first string" ;
String s2 = "My other string..." ;
// Let's work with sequences of 2 characters...
Cosine cosine = new Cosine ( 2 );
// Pre-compute the profile of strings
Map < String , Integer > profile1 = cosine . getProfile ( s1 );
Map < String , Integer > profile2 = cosine . getProfile ( s2 );
// Prints 0.516185
System . out . println ( cosine . similarity ( profile1 , profile2 ));
}
}Attention, cela ne fonctionne que si le même objet KShingling est utilisé pour analyser toutes les chaînes d'entrée !
Distance Q-gram, telle que définie par Ukkonen dans "Correspondance approximative des chaînes avec q-grammes et correspondances maximales" http://www.sciencedirect.com/science/article/pii/0304397592901434
La distance entre deux chaînes est définie comme la norme L1 de la différence de leurs profils (le nombre d'occurrences de chaque n-gramme) : SUM( |V1_i - V2_i| ). La distance Q-gram est une limite inférieure de la distance de Levenshtein, mais peut être calculée en O(m + n), où Levenshtein nécessite O(mn)
La similarité entre les deux chaînes est le cosinus de l'angle entre la représentation de ces deux vecteurs et est calculée comme V1 . V2 / (|V1| * |V2|)
La distance est calculée comme 1 - similarité cosinus.
Comme la distance Q-Gram, les chaînes d'entrée sont d'abord converties en ensembles de n-grammes (séquences de n caractères, également appelées k-shingles), mais cette fois la cardinalité de chaque n-gramme n'est pas prise en compte. Chaque chaîne d'entrée est simplement un ensemble de n-grammes. L'indice Jaccard est alors calculé comme |V1 inter V2| / |V1 syndicat V2|.
La distance est calculée comme 1 - similarité. L'indice Jaccard est une distance métrique.
Similaire à l'indice Jaccard, mais cette fois la similarité est calculée comme 2 * |V1 inter V2| / (|V1| + |V2|).
La distance est calculée comme 1 - similarité.
Ratcliff/Obershelp Pattern Recognition, également connu sous le nom de Gestalt Pattern Matching, est un algorithme de correspondance de chaînes permettant de déterminer la similarité de deux chaînes. Il a été développé en 1983 par John W. Ratcliff et John A. Obershelp et publié dans le Dr. Dobb's Journal en juillet 1988.
Ratcliff/Obershelp calcule la similarité entre 2 chaînes et la valeur renvoyée se situe dans l'intervalle [0.0, 1.0].
La distance est calculée comme suit : 1 - similarité Ratcliff/Obershelp.
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
RatcliffObershelp ro = new RatcliffObershelp ();
// substitution of s and t
System . out . println ( ro . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( ro . similarity ( "My string" , "My ntrisg" ));
}
}produira :
0.8888888888888888
0.7777777777777778
SIFT4 est un algorithme de distance de chaîne à usage général inspiré de JaroWinkler et de Longest Common Subsequence. Il a été développé pour produire une mesure de distance qui correspond le plus possible à la perception humaine de la distance entre les cordes. Par conséquent, il prend en compte des éléments tels que la substitution de caractères, la distance entre les caractères, la sous-séquence commune la plus longue, etc. Il a été développé à l'aide de tests expérimentaux et sans fondement théorique.
import info.debatty.java.stringsimilarity.experimental.Sift4;
public class MyApp {
public static void main(String[] args) {
String s1 = "This is the first string";
String s2 = "And this is another string";
Sift4 sift4 = new Sift4();
sift4.setMaxOffset(5);
double expResult = 11.0;
double result = sift4.distance(s1, s2);
assertEquals(expResult, result, 0.0);
}
}
Utilisez la similarité de chaînes Java dans votre projet et souhaitez que cela soit mentionné ici ? N'hésitez pas à me laisser un message !
