java string similarity
v2.0.0
Eine Bibliothek, die verschiedene String-Ähnlichkeits- und Distanzmaße implementiert. Ein Dutzend Algorithmen (einschließlich Levenshtein-Edit-Distanz und Geschwister, Jaro-Winkler, Longest Common Subsequence, Cosinus-Ähnlichkeit usw.) sind derzeit implementiert. Die vollständige Liste finden Sie in der Übersichtstabelle unten ...
Mit Maven:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
Oder schauen Sie sich die Veröffentlichungen an.
Diese Bibliothek erfordert Java 8 oder höher.
Die Hauptmerkmale jedes implementierten Algorithmus werden im Folgenden dargestellt. Die Spalte „Kosten“ gibt eine Schätzung des Rechenaufwands zur Berechnung der Ähnlichkeit zwischen zwei Zeichenfolgen der Länge m bzw. n an.
| Normalisiert? | Metrisch? | Typ | Kosten | Typische Verwendung | ||
|---|---|---|---|---|---|---|
| Levenstein | Distanz | NEIN | Ja | O(m*n) 1 | ||
| Normalisiertes Levenshtein | Distanz Ähnlichkeit | Ja | NEIN | O(m*n) 1 | ||
| Gewichtetes Levenshtein | Distanz | NEIN | NEIN | O(m*n) 1 | OCR | |
| Damerau-Levenshtein 3 | Distanz | NEIN | Ja | O(m*n) 1 | ||
| Optimale Saitenausrichtung 3 | Distanz | NEIN | NEIN | O(m*n) 1 | ||
| Jaro-Winkler | Ähnlichkeit Distanz | Ja | NEIN | O(m*n) | Tippfehlerkorrektur | |
| Längste gemeinsame Folge | Distanz | NEIN | NEIN | O(m*n) 1,2 | Diff-Dienstprogramm, GIT-Abgleich | |
| Metrische längste gemeinsame Folge | Distanz | Ja | Ja | O(m*n) 1,2 | ||
| N-Gramm | Distanz | Ja | NEIN | O(m*n) | ||
| Q-Gramm | Distanz | NEIN | NEIN | Profil | O(m+n) | |
| Kosinusähnlichkeit | Ähnlichkeit Distanz | Ja | NEIN | Profil | O(m+n) | |
| Jaccard-Index | Ähnlichkeit Distanz | Ja | Ja | Satz | O(m+n) | |
| Sorensen-Dice-Koeffizient | Ähnlichkeit Distanz | Ja | NEIN | Satz | O(m+n) | |
| Ratcliff-Obershelp | Ähnlichkeit Distanz | Ja | NEIN | ? |
[1] In dieser Bibliothek werden die Levenshtein-Bearbeitungsentfernung, die LCS-Entfernung und ihre Geschwister mithilfe der dynamischen Programmiermethode berechnet, die einen Aufwand von O(mn) hat. Für den Levenshtein-Abstand wird der Algorithmus manchmal als Wagner-Fischer-Algorithmus („The String-to-String Correction Problem“, 1974) bezeichnet. Der ursprüngliche Algorithmus verwendet eine Matrix der Größe mxn, um den Levenshtein-Abstand zwischen Zeichenfolgenpräfixen zu speichern.
Wenn das Alphabet endlich ist, ist es möglich, die Methode von Four Russians (Arlazarov et al. „On Economic Construction of the transitive Schließung eines gerichteten Graphen“, 1970) zu verwenden, um die Berechnung zu beschleunigen. Dies wurde 1980 von Masek veröffentlicht („A Faster Algorithm Computing String Edit Distances“). Diese Methode teilt die Matrix in Blöcke der Größe tx t auf. Jeder mögliche Block wird vorberechnet, um eine Nachschlagetabelle zu erstellen. Diese Nachschlagetabelle kann dann verwendet werden, um die String-Ähnlichkeit (oder den Abstand) in O(nm/t) zu berechnen. Normalerweise wird t als log(m) gewählt, wenn m > n. Der resultierende Rechenaufwand beträgt somit O(mn/log(m)). Diese Methode wurde (noch) nicht implementiert.
[2] In „Length of Maximal Common Subsequences“ schlug KS Larsen einen Algorithmus vor, der die Länge von LCS in der Zeit O(log(m).log(n)) berechnet. Allerdings hat der Algorithmus einen Speicherbedarf O(m.n²) und wurde daher hier nicht implementiert.
[3] Es gibt zwei Varianten des Damerau-Levenshtein-Saitenabstands: Damerau-Levenshtein mit benachbarten Transpositionen (manchmal auch als uneingeschränkter Damerau-Levenshtein-Abstand bezeichnet) und optimale Saitenausrichtung (manchmal auch als eingeschränkter Bearbeitungsabstand bezeichnet). Für eine optimale String-Ausrichtung kann kein Teilstring mehr als einmal bearbeitet werden.
Obwohl das Thema einfach erscheinen mag, gibt es viele verschiedene Algorithmen, um Textähnlichkeit oder -entfernung zu messen. Daher definiert die Bibliothek einige Schnittstellen, um sie zu kategorisieren.
Im Allgemeinen implementieren Algorithmen, die NormalizedStringSimilarity implementieren, auch NormalizedStringDistance und Ähnlichkeit = 1 – Abstand. Aber es gibt ein paar Ausnahmen, wie z. B. N-Gram-Ähnlichkeit und -Distanz (Kondrak) ...
Die MetricStringDistance-Schnittstelle: Einige der Abstände sind tatsächlich metrische Abstände, was bedeutet, dass die Dreiecksungleichung d(x, y) <= d(x,z) + d(z,y) überprüft wird. Levenshtein ist beispielsweise eine metrische Distanz, NormalizedLevenshtein jedoch nicht.
Viele Suchalgorithmen und Indexierungsstrukturen für den nächsten Nachbarn basieren auf der Dreiecksungleichung. Sie können sich „Similarity Search, The Metric Space Approach“ von Zezula et al. ansehen. für eine Umfrage. Diese können nicht mit nichtmetrischen Ähnlichkeitsmaßen verwendet werden.
Eine detaillierte Beschreibung finden Sie im Javadoc
Einige Algorithmen funktionieren, indem sie Zeichenfolgen in Mengen von n-Grammen (Folgen von n Zeichen, manchmal auch k-Schindeln genannt) umwandeln. Die Ähnlichkeit oder der Abstand zwischen den Saiten ist dann die Ähnlichkeit oder der Abstand zwischen den Sätzen.
Einige von ihnen, wie beispielsweise Jaccard, betrachten Saiten als Schindelsätze und berücksichtigen nicht die Häufigkeit des Vorkommens jeder Schindel. Andere, wie die Kosinusähnlichkeit, arbeiten mit dem sogenannten Profil der Saiten, das die Häufigkeit des Vorkommens jeder Schindel berücksichtigt.
Für diese Algorithmen ist beim Umgang mit großen Datensätzen ein weiterer Anwendungsfall möglich:
Der Levenshtein-Abstand zwischen zwei Wörtern ist die Mindestanzahl der Einzelzeichenbearbeitungen (Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern.
Es handelt sich um einen metrischen Saitenabstand. Diese Implementierung verwendet dynamische Programmierung (Wagner-Fischer-Algorithmus) mit nur zwei Datenzeilen. Der Platzbedarf beträgt somit O(m) und der Algorithmus läuft in 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" ));
}
}Dieser Abstand wird als Levenshtein-Abstand dividiert durch die Länge der längsten Saite berechnet. Der resultierende Wert liegt immer im Intervall [0,0 1,0], ist aber keine Metrik mehr!
Die Ähnlichkeit wird als 1 – normalisierter Abstand berechnet.
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" ));
}
}Eine Implementierung von Levenshtein, die es ermöglicht, unterschiedliche Gewichtungen für verschiedene Zeichenersetzungen zu definieren.
Dieser Algorithmus wird normalerweise für Anwendungen zur optischen Zeichenerkennung (OCR) verwendet. Bei OCR sind die Kosten für die Ersetzung von P und R niedriger als die Kosten für die Ersetzung von P und M, da P aus Sicht der OCR R ähnlich ist.
Es kann auch zur automatischen Korrektur von Tastatureingaben verwendet werden. Hier ist der Aufwand für das Ersetzen von E und R geringer, da diese beispielsweise auf einer AZERTY- oder QWERTZ-Tastatur nebeneinander liegen. Daher ist die Wahrscheinlichkeit höher, dass der Benutzer die Zeichen falsch eingegeben hat.
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" ));
}
}Ähnlich wie bei Levenshtein ist der Damerau-Levenshtein-Abstand mit Transposition (manchmal auch als uneingeschränkter Damerau-Levenshtein-Abstand bezeichnet) die Mindestanzahl von Operationen, die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln, wobei eine Operation als Einfügen, Löschen oder Ersetzen von a definiert ist einzelnes Zeichen oder eine Vertauschung zweier benachbarter Zeichen .
Es respektiert die Dreiecksungleichung und ist daher ein metrischer Abstand.
Dies ist nicht mit dem optimalen String-Ausrichtungsabstand zu verwechseln, bei dem es sich um eine Erweiterung handelt, bei der kein Teilstring mehr als einmal bearbeitet werden kann.
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" ));
}
}Wird produzieren:
1.0
2.0
1.0
1.0
1.0
6.0
Die optimale String-Ausrichtungsvariante von Damerau-Levenshtein (manchmal auch als eingeschränkter Bearbeitungsabstand bezeichnet) berechnet die Anzahl der Bearbeitungsvorgänge, die erforderlich sind, um die Zeichenfolgen unter der Bedingung gleich zu machen, dass kein Teilstring mehr als einmal bearbeitet wird , während die echte Damerau-Levenshtein-Variante keine solche aufweist Beschränkung. Der Unterschied zum Algorithmus für die Levenshtein-Distanz besteht in der Hinzufügung einer Wiederholung für die Transpositionsoperationen.
Beachten Sie, dass für den optimalen String-Ausrichtungsabstand die Dreiecksungleichung nicht gilt und es sich daher nicht um eine echte Metrik handelt.
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" ));;
}
}Wird produzieren:
3.0
Jaro-Winkler ist ein String-Edit-Abstand, der im Bereich der Datensatzverknüpfung (Duplikaterkennung) entwickelt wurde (Winkler, 1990). Die Jaro-Winkler-Distanzmetrik ist für kurze Zeichenfolgen wie Personennamen und zum Erkennen von Transpositionstippfehlern konzipiert und am besten geeignet.
Jaro-Winkler berechnet die Ähnlichkeit zwischen zwei Zeichenfolgen und der zurückgegebene Wert liegt im Intervall [0,0, 1,0]. Es handelt sich (ungefähr) um eine Variante von Damerau-Levenshtein, bei der die Transposition zweier nahe beieinander liegender Zeichen als weniger wichtig angesehen wird als die Transposition zweier weit voneinander entfernter Zeichen. Jaro-Winkler bestraft Ergänzungen oder Ersetzungen, die nicht als Transpositionen ausgedrückt werden können.
Der Abstand wird als 1 – Jaro-Winkler-Ähnlichkeit berechnet.
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" ));
}
}wird produzieren:
0.9740740656852722
0.8962963223457336
Das Problem der längsten gemeinsamen Teilsequenz (LCS) besteht darin, die längste Teilsequenz zu finden, die zwei (oder mehr) Sequenzen gemeinsam ist. Es unterscheidet sich von Problemen beim Finden gemeinsamer Teilzeichenfolgen: Im Gegensatz zu Teilzeichenfolgen müssen Teilsequenzen keine aufeinanderfolgenden Positionen innerhalb der Originalsequenzen einnehmen.
Es wird vom Diff-Dienstprogramm, von Git zum Abgleichen mehrerer Änderungen usw. verwendet.
Der LCS-Abstand zwischen den Zeichenfolgen X (der Länge n) und Y (der Länge m) beträgt n + m – 2 |LCS(X, Y)| min = 0 max = n + m
Der LCS-Abstand entspricht dem Levenshtein-Abstand, wenn nur Einfügung und Löschung zulässig sind (keine Ersetzung) oder wenn die Kosten der Ersetzung das Doppelte der Kosten einer Einfügung oder Löschung betragen.
Diese Klasse implementiert den dynamischen Programmieransatz, der einen Platzbedarf O(mn) und einen Rechenaufwand O(mn) hat.
In „Length of Maximal Common Subsequences“ schlug KS Larsen einen Algorithmus vor, der die Länge von LCS in der Zeit O(log(m).log(n)) berechnet. Allerdings hat der Algorithmus einen Speicherbedarf O(m.n²) und wurde daher hier nicht implementiert.
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" ));
}
}Distanzmetrik basierend auf Longest Common Subsequence, aus den Notizen „An LCS-based string metric“ von Daniel Bakkelund. http://heim.ifi.uio.no/~danielry/StringMetric.pdf
Der Abstand wird als 1 - |LCS(s1, s2)| berechnet / 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" ));
}
}Normalisierter N-Gram-Abstand gemäß Kondrak, „N-Gram Similarity and Distance“, String Processing and Information Retrieval, Lecture Notes in Computer Science, Band 3772, 2005, S. 115–126.
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
Der Algorithmus verwendet das Anhängen des Sonderzeichens „n“, um die Gewichtung der ersten Zeichen zu erhöhen. Die Normalisierung wird erreicht, indem der Gesamtähnlichkeitswert durch die ursprüngliche Länge des längsten Wortes dividiert wird.
In dem Papier definiert Kondrak auch ein Ähnlichkeitsmaß, das (noch) nicht implementiert ist.
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 ));
}
}Einige Algorithmen funktionieren, indem sie Zeichenfolgen in Mengen von n-Grammen (Folgen von n Zeichen, manchmal auch k-Schindeln genannt) umwandeln. Die Ähnlichkeit oder der Abstand zwischen den Saiten ist dann die Ähnlichkeit oder der Abstand zwischen den Sätzen.
Der Aufwand für die Berechnung dieser Ähnlichkeiten und Abstände wird hauptsächlich durch k-Shingling (Umwandeln der Zeichenfolgen in Folgen von k Zeichen) verursacht. Daher gibt es typischerweise zwei Anwendungsfälle für diese Algorithmen:
Berechnen Sie direkt den Abstand zwischen Saiten:
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" ));
}
}Oder berechnen Sie bei großen Datensätzen das Profil aller Zeichenfolgen vorab. Die Ähnlichkeit zwischen Profilen kann dann berechnet werden:
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 ));
}
}Beachten Sie, dass dies nur funktioniert, wenn dasselbe KShingling-Objekt zum Parsen aller Eingabezeichenfolgen verwendet wird!
Q-Gramm-Abstand, wie von Ukkonen in „Approximate string-matching with q-grams and maximale Matches“ definiert: http://www.sciencedirect.com/science/article/pii/0304397592901434
Der Abstand zwischen zwei Strings ist als L1-Norm der Differenz ihrer Profile definiert (die Anzahl der Vorkommen jedes n-Gramms): SUM( |V1_i - V2_i| ). Der Q-Gramm-Abstand ist eine untere Grenze des Levenshtein-Abstands, kann aber in O(m + n) berechnet werden, wobei Levenshtein O(mn) erfordert.
Die Ähnlichkeit zwischen den beiden Zeichenfolgen ist der Kosinus des Winkels zwischen der Darstellung dieser beiden Vektoren und wird als V1 berechnet. V2 / (|V1| * |V2|)
Der Abstand wird als 1-Kosinus-Ähnlichkeit berechnet.
Wie bei der Q-Gram-Distanz werden die Eingabezeichenfolgen zunächst in Sätze von n-Grammen (Folgen von n Zeichen, auch k-Schindeln genannt) umgewandelt, diesmal wird jedoch die Kardinalität jedes n-Gramms nicht berücksichtigt. Jede Eingabezeichenfolge ist einfach eine Menge von n-Grammen. Der Jaccard-Index wird dann als |V1 inter V2| berechnet / |V1 Vereinigung V2|.
Die Entfernung wird als 1 – Ähnlichkeit berechnet. Der Jaccard-Index ist eine metrische Distanz.
Ähnlich dem Jaccard-Index, aber dieses Mal wird die Ähnlichkeit als 2 * |V1 inter V2| berechnet / (|V1| + |V2|).
Die Entfernung wird als 1 – Ähnlichkeit berechnet.
Ratcliff/Obershelp Pattern Recognition, auch bekannt als Gestalt Pattern Matching, ist ein String-Matching-Algorithmus zur Bestimmung der Ähnlichkeit zweier Strings. Es wurde 1983 von John W. Ratcliff und John A. Obershelp entwickelt und im Juli 1988 im Dr. Dobb's Journal veröffentlicht
Ratcliff/Obershelp berechnet die Ähnlichkeit zwischen zwei Zeichenfolgen und der zurückgegebene Wert liegt im Intervall [0,0, 1,0].
Der Abstand wird als 1 – Ratcliff/Obershelp-Ähnlichkeit berechnet.
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" ));
}
}wird produzieren:
0.8888888888888888
0.7777777777777778
SIFT4 ist ein Allzweck-String-Distance-Algorithmus, der von JaroWinkler und Longest Common Subsequence inspiriert ist. Es wurde entwickelt, um ein Abstandsmaß zu erzeugen, das der menschlichen Wahrnehmung des Saitenabstands möglichst nahe kommt. Daher berücksichtigt es Elemente wie Zeichenersetzung, Zeichenabstand, längste gemeinsame Teilsequenz usw. Es wurde mithilfe experimenteller Tests und ohne theoretischen Hintergrund entwickelt.
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);
}
}
Verwenden Sie Java-String-Ähnlichkeit in Ihrem Projekt und möchten Sie, dass es hier erwähnt wird? Zögern Sie nicht, mir eine Nachricht zu schreiben!
