java string similarity
v2.0.0
Una biblioteca que implementa diferentes medidas de distancia y similitud de cadenas. Actualmente se implementan una docena de algoritmos (incluidos la distancia de edición de Levenshtein y los hermanos, Jaro-Winkler, la subsecuencia común más larga, la similitud del coseno, etc.). Consulte la tabla resumen a continuación para ver la lista completa...
Usando experto:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
O consultar los lanzamientos.
Esta biblioteca requiere Java 8 o más reciente.
Las principales características de cada algoritmo implementado se presentan a continuación. La columna "costo" proporciona una estimación del costo computacional para calcular la similitud entre dos cadenas de longitud myn respectivamente.
| ¿Normalizado? | ¿Métrico? | Tipo | Costo | Uso típico | ||
|---|---|---|---|---|---|---|
| Levenstein | distancia | No | Sí | O(m*n) 1 | ||
| Levenshtein normalizado | distancia semejanza | Sí | No | O(m*n) 1 | ||
| Levenshtein ponderado | distancia | No | No | O(m*n) 1 | LOC | |
| Damerau-Levenshtein 3 | distancia | No | Sí | O(m*n) 1 | ||
| Alineación óptima de cuerdas 3 | distancia | No | No | O(m*n) 1 | ||
| Jaro Winkler | semejanza distancia | Sí | No | O(m*n) | corrección de errores tipográficos | |
| Subsecuencia común más larga | distancia | No | No | O(m*n) 1,2 | utilidad diff, conciliación GIT | |
| Subsecuencia común más larga métrica | distancia | Sí | Sí | O(m*n) 1,2 | ||
| N-Gramo | distancia | Sí | No | O(m*n) | ||
| Q-Gramo | distancia | No | No | Perfil | O(m+n) | |
| Similitud del coseno | semejanza distancia | Sí | No | Perfil | O(m+n) | |
| índice jaccard | semejanza distancia | Sí | Sí | Colocar | O(m+n) | |
| Coeficiente de Sorensen-Dice | semejanza distancia | Sí | No | Colocar | O(m+n) | |
| Ayuda de Ratcliff-Obers | semejanza distancia | Sí | No | ? |
[1] En esta biblioteca, la distancia de edición de Levenshtein, la distancia LCS y sus hermanos se calculan utilizando el método de programación dinámica , que tiene un costo O (mn). Para la distancia de Levenshtein, el algoritmo a veces se denomina algoritmo de Wagner-Fischer ("El problema de corrección de cadena a cadena", 1974). El algoritmo original utiliza una matriz de tamaño mxn para almacenar la distancia de Levenshtein entre prefijos de cadenas.
Si el alfabeto es finito, es posible utilizar el método de los cuatro rusos (Arlazarov et al. "Sobre la construcción económica del cierre transitivo de un grafo dirigido", 1970) para acelerar el cálculo. Esto fue publicado por Masek en 1980 ("Un algoritmo más rápido para calcular distancias de edición de cadenas"). Este método divide la matriz en bloques de tamaño tx t. Cada bloque posible se calcula previamente para producir una tabla de búsqueda. Esta tabla de búsqueda se puede utilizar para calcular la similitud (o distancia) de la cadena en O (nm/t). Normalmente, t se elige como log(m) si m > n. El coste de cálculo resultante es, por tanto, O(mn/log(m)). Este método no se ha implementado (aún).
[2] En "Longitud de las subsecuencias comunes máximas", KS Larsen propuso un algoritmo que calcula la longitud de LCS en el tiempo O(log(m).log(n)). Pero el algoritmo tiene un requisito de memoria O(m.n²) y por lo tanto no se implementó aquí.
[3] Hay dos variantes de la distancia de cuerda Damerau-Levenshtein: Damerau-Levenshtein con transposiciones adyacentes (a veces también llamada distancia Damerau-Levenshtein sin restricciones) y Alineación óptima de cuerdas (a veces también llamada distancia de edición restringida). Para una alineación óptima de cadenas, no se puede editar ninguna subcadena más de una vez.
Aunque el tema puede parecer simple, existen muchos algoritmos diferentes para medir la similitud o distancia del texto. Por lo tanto la biblioteca define algunas interfaces para categorizarlos.
Generalmente, los algoritmos que implementan NormalizedStringSimilarity también implementan NormalizedStringDistance y similitud = 1 - distancia. Pero hay algunas excepciones, como la similitud y distancia de N-Gram (Kondrak)...
La interfaz MetricStringDistance: algunas de las distancias son en realidad distancias métricas, lo que significa que se debe verificar la desigualdad del triángulo d(x, y) <= d(x,z) + d(z,y). Por ejemplo, Levenshtein es una distancia métrica, pero NormalizedLevenshtein no lo es.
Muchos algoritmos de búsqueda de vecinos más cercanos y estructuras de indexación se basan en la desigualdad del triángulo. Puede consultar "Búsqueda de similitudes, el enfoque del espacio métrico" de Zezula et al. para una encuesta. Estos no se pueden utilizar con medidas de similitud no métricas.
Lea Javadoc para obtener una descripción detallada.
Algunos algoritmos funcionan convirtiendo cadenas en conjuntos de n-gramas (secuencias de n caracteres, a veces también llamadas k-shingles). La similitud o distancia entre las cuerdas es entonces la similitud o distancia entre los conjuntos.
Algunos de ellos, como jaccard, consideran las cuerdas como conjuntos de tejas y no consideran el número de apariciones de cada teja. Otros, como la similitud del coseno, funcionan utilizando lo que a veces se llama el perfil de las cuerdas, que tiene en cuenta el número de apariciones de cada teja.
Para estos algoritmos, es posible otro caso de uso cuando se trata de grandes conjuntos de datos:
La distancia de Levenshtein entre dos palabras es el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra.
Es una distancia de cuerda métrica. Esta implementación utiliza programación dinámica (algoritmo de Wagner-Fischer), con solo 2 filas de datos. Por tanto, el requisito de espacio es O(m) y el algoritmo se ejecuta 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" ));
}
}Esta distancia se calcula como la distancia de Levenshtein dividida por la longitud de la cuerda más larga. El valor resultante siempre está en el intervalo [0.0 1.0] ¡pero ya no es una métrica!
La similitud se calcula como 1 - distancia normalizada.
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" ));
}
}Una implementación de Levenshtein que permite definir diferentes pesos para diferentes sustituciones de caracteres.
Este algoritmo se utiliza normalmente para aplicaciones de reconocimiento óptico de caracteres (OCR). Para OCR, el costo de sustituir P y R es menor que el costo de sustituir P y M, por ejemplo, porque desde el punto de vista de OCR, P es similar a R.
También se puede utilizar para la autocorrección de escritura en el teclado. Aquí el coste de sustituir E y R es menor, por ejemplo porque están situados uno al lado del otro en un teclado AZERTY o QWERTY. Por tanto, la probabilidad de que el usuario haya escrito mal los caracteres es mayor.
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" ));
}
}Similar a Levenshtein, la distancia Damerau-Levenshtein con transposición (a veces también llamada distancia Damerau-Levenshtein sin restricciones) es el número mínimo de operaciones necesarias para transformar una cadena en otra, donde una operación se define como una inserción, eliminación o sustitución de una un solo carácter o una transposición de dos caracteres adyacentes .
Respeta la desigualdad del triángulo y, por tanto, es una distancia métrica.
Esto no debe confundirse con la distancia óptima de alineación de cadenas, que es una extensión en la que ninguna subcadena se puede editar más de una vez.
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" ));
}
}Producirá:
1.0
2.0
1.0
1.0
1.0
6.0
La variante de alineación óptima de cadenas de Damerau-Levenshtein (a veces llamada distancia de edición restringida) calcula el número de operaciones de edición necesarias para hacer que las cadenas sean iguales bajo la condición de que ninguna subcadena se edite más de una vez , mientras que el verdadero Damerau-Levenshtein no presenta tal restricción. La diferencia con el algoritmo para la distancia de Levenshtein es la adición de una recurrencia para las operaciones de transposición.
Tenga en cuenta que para la distancia óptima de alineación de cuerdas, la desigualdad del triángulo no se cumple y, por lo tanto, no es una métrica verdadera.
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" ));;
}
}Producirá:
3.0
Jaro-Winkler es una distancia de edición de cadenas que se desarrolló en el área de vinculación de registros (detección de duplicados) (Winkler, 1990). La métrica de distancia Jaro-Winkler está diseñada y es más adecuada para cadenas cortas, como nombres de personas, y para detectar errores tipográficos de transposición.
Jaro-Winkler calcula la similitud entre 2 cadenas y el valor devuelto se encuentra en el intervalo [0.0, 1.0]. Es (aproximadamente) una variación de Damerau-Levenshtein, donde la transposición de 2 personajes cercanos se considera menos importante que la transposición de 2 personajes que están lejos uno del otro. Jaro-Winkler penaliza las adiciones o sustituciones que no puedan expresarse como transposiciones.
La distancia se calcula como 1 - similitud de 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" ));
}
}producirá:
0.9740740656852722
0.8962963223457336
El problema de la subsecuencia común más larga (LCS) consiste en encontrar la subsecuencia más larga común a dos (o más) secuencias. Se diferencia de los problemas de encontrar subcadenas comunes: a diferencia de las subcadenas, no es necesario que las subsecuencias ocupen posiciones consecutivas dentro de las secuencias originales.
Lo utiliza la utilidad diff, Git para conciliar múltiples cambios, etc.
La distancia LCS entre las cadenas X (de longitud n) e Y (de longitud m) es n + m - 2 |LCS(X, Y)| mín = 0 máx = n + m
La distancia LCS es equivalente a la distancia de Levenshtein cuando solo se permite la inserción y eliminación (no sustitución), o cuando el costo de la sustitución es el doble del costo de una inserción o eliminación.
Esta clase implementa el enfoque de programación dinámica, que tiene un requisito de espacio O (mn) y un costo de cálculo O (mn).
En "Longitud de las subsecuencias comunes máximas", KS Larsen propuso un algoritmo que calcula la longitud de LCS en el tiempo O(log(m).log(n)). Pero el algoritmo tiene un requisito de memoria O(m.n²) y por lo tanto no se implementó aquí.
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étrica de distancia basada en la subsecuencia común más larga, de las notas "Una métrica de cadena basada en LCS" de Daniel Bakkelund. http://heim.ifi.uio.no/~danielry/StringMetric.pdf
La distancia se calcula como 1 - |LCS(s1, s2)| / máx(|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" ));
}
}Distancia de N-Gram normalizada según la definición de Kondrak, "N-Gram Similarity and Distance", String Processing and Information Retrieval, Lecture Notes in Computer Science Volumen 3772, 2005, págs. 115-126.
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
El algoritmo utiliza la adición del carácter especial 'n' para aumentar el peso de los primeros caracteres. La normalización se logra dividiendo la puntuación de similitud total por la longitud original de la palabra más larga.
En el artículo, Kondrak también define una medida de similitud, que aún no se ha implementado.
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 ));
}
}Algunos algoritmos funcionan convirtiendo cadenas en conjuntos de n-gramas (secuencias de n caracteres, a veces también llamadas k-shingles). La similitud o distancia entre las cuerdas es entonces la similitud o distancia entre los conjuntos.
El costo de calcular estas similitudes y distancias está dominado principalmente por k-shingling (convertir las cadenas en secuencias de k caracteres). Por lo tanto, normalmente existen dos casos de uso para estos algoritmos:
Calcule directamente la distancia entre cuerdas:
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" ));
}
}O, para conjuntos de datos grandes, calcule previamente el perfil de todas las cadenas. Luego se puede calcular la similitud entre perfiles:
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 ));
}
}¡Preste atención, esto solo funciona si se usa el mismo objeto KShingling para analizar todas las cadenas de entrada!
Distancia de Q-grama, según lo define Ukkonen en "Coincidencia aproximada de cadenas con q-gramas y coincidencias máximas" http://www.sciencedirect.com/science/article/pii/0304397592901434
La distancia entre dos cadenas se define como la norma L1 de la diferencia de sus perfiles (el número de apariciones de cada n-grama): SUM( |V1_i - V2_i| ). La distancia Q-gramo es un límite inferior de la distancia de Levenshtein, pero se puede calcular en O(m + n), donde Levenshtein requiere O(mn)
La similitud entre las dos cadenas es el coseno del ángulo entre la representación de estos dos vectores y se calcula como V1. V2 / (|V1| * |V2|)
La distancia se calcula como 1 - similitud coseno.
Al igual que la distancia Q-Gram, las cadenas de entrada se convierten primero en conjuntos de n-gramas (secuencias de n caracteres, también llamadas k-shingles), pero esta vez no se tiene en cuenta la cardinalidad de cada n-grama. Cada cadena de entrada es simplemente un conjunto de n-gramas. El índice de Jaccard se calcula entonces como |V1 entre V2| / |V1 unión V2|.
La distancia se calcula como 1 - similitud. El índice de Jaccard es una distancia métrica.
Similar al índice de Jaccard, pero esta vez la similitud se calcula como 2 * |V1 inter V2| / (|V1| + |V2|).
La distancia se calcula como 1 - similitud.
El reconocimiento de patrones de Ratcliff/Obershelp, también conocido como coincidencia de patrones Gestalt, es un algoritmo de coincidencia de cadenas para determinar la similitud de dos cadenas. Fue desarrollado en 1983 por John W. Ratcliff y John A. Obershelp y publicado en el Dr. Dobb's Journal en julio de 1988.
Ratcliff/Obershelp calcula la similitud entre 2 cadenas y el valor devuelto se encuentra en el intervalo [0.0, 1.0].
La distancia se calcula como 1 - similitud 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" ));
}
}producirá:
0.8888888888888888
0.7777777777777778
SIFT4 es un algoritmo de distancia de cadenas de propósito general inspirado en JaroWinkler y Longest Common Subsequence. Fue desarrollado para producir una medida de distancia que se acerque lo más posible a la percepción humana de la distancia de las cuerdas. Por lo tanto, tiene en cuenta elementos como la sustitución de caracteres, la distancia de los caracteres, la subsecuencia común más larga, etc. Se desarrolló mediante pruebas experimentales y sin fundamento teórico.
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);
}
}
¿Utiliza java-string-similarity en su proyecto y quiere que se mencione aquí? ¡No dudes en escribirme!
