java string similarity
v2.0.0
Uma biblioteca que implementa diferentes medidas de similaridade e distância de strings. Uma dúzia de algoritmos (incluindo distância de edição e irmãos de Levenshtein, Jaro-Winkler, maior subsequência comum, similaridade de cosseno, etc.) estão atualmente implementados. Verifique a tabela de resumo abaixo para a lista completa...
Usando maven:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
Ou confira os lançamentos.
Esta biblioteca requer Java 8 ou mais recente.
As principais características de cada algoritmo implementado são apresentadas a seguir. A coluna "custo" fornece uma estimativa do custo computacional para calcular a similaridade entre duas strings de comprimento m e n, respectivamente.
| Normalizado? | Métrica? | Tipo | Custo | Uso típico | ||
|---|---|---|---|---|---|---|
| Levenshtein | distância | Não | Sim | O(m*n) 1 | ||
| Levenshtein normalizado | distância semelhança | Sim | Não | O(m*n) 1 | ||
| Levenshtein ponderado | distância | Não | Não | O(m*n) 1 | OCR | |
| Damerau-Levenstein 3 | distância | Não | Sim | O(m*n) 1 | ||
| Alinhamento ideal de cordas 3 | distância | Não | Não | O(m*n) 1 | ||
| Jaro Winkler | semelhança distância | Sim | Não | O(m*n) | correção de erro de digitação | |
| Subsequência Comum Mais Longa | distância | Não | Não | O(m*n) 1,2 | utilitário diff, reconciliação GIT | |
| Subsequência comum mais longa da métrica | distância | Sim | Sim | O(m*n) 1,2 | ||
| N-grama | distância | Sim | Não | O(m*n) | ||
| Q-grama | distância | Não | Não | Perfil | O(m+n) | |
| Semelhança de cosseno | semelhança distância | Sim | Não | Perfil | O(m+n) | |
| Índice Jaccard | semelhança distância | Sim | Sim | Definir | O(m+n) | |
| Coeficiente de Sorensen-Dados | semelhança distância | Sim | Não | Definir | O(m+n) | |
| Ratcliff-Obersajuda | semelhança distância | Sim | Não | ? |
[1] Nesta biblioteca, a distância de edição de Levenshtein, a distância LCS e seus irmãos são calculados usando o método de programação dinâmica , que tem um custo O(mn). Para a distância de Levenshtein, o algoritmo às vezes é chamado de algoritmo Wagner-Fischer ("O problema de correção string-to-string", 1974). O algoritmo original usa uma matriz de tamanho mxn para armazenar a distância de Levenshtein entre prefixos de string.
Se o alfabeto for finito, é possível usar o método dos quatro russos (Arlazarov et al. "Sobre a construção econômica do fechamento transitivo de um grafo direcionado", 1970) para acelerar o cálculo. Este foi publicado por Masek em 1980 ("A Faster Algorithm Computing String Edit Distances"). Este método divide a matriz em blocos de tamanho tx t. Cada bloco possível é pré-computado para produzir uma tabela de consulta. Esta tabela de pesquisa pode então ser usada para calcular a similaridade (ou distância) da string em O (nm/t). Normalmente, t é escolhido como log(m) se m > n. O custo de cálculo resultante é, portanto, O(mn/log(m)). Este método (ainda) não foi implementado.
[2] Em "Length of Maximal Common Subsequences", KS Larsen propôs um algoritmo que calcula o comprimento de LCS no tempo O(log(m).log(n)). Mas o algoritmo tem um requisito de memória O(m.n²) e, portanto, não foi implementado aqui.
[3] Existem duas variantes da distância das cordas Damerau-Levenshtein: Damerau-Levenshtein com transposições adjacentes (às vezes também chamada de distância Damerau-Levenshtein irrestrita) e Alinhamento ideal das cordas (às vezes também chamado de distância de edição restrita). Para o alinhamento ideal de strings, nenhuma substring pode ser editada mais de uma vez.
Embora o tópico possa parecer simples, existem muitos algoritmos diferentes para medir a semelhança ou distância do texto. Portanto a biblioteca define algumas interfaces para categorizá-los.
Geralmente, algoritmos que implementam NormalizedStringSimilarity também implementam NormalizedStringDistance e similaridade = 1 - distância. Mas há algumas exceções, como similaridade e distância de N-Gram (Kondrak)...
A interface MetricStringDistance: algumas das distâncias são na verdade distâncias métricas, o que significa que verifica a desigualdade triangular d(x, y) <= d(x,z) + d(z,y). Por exemplo, Levenshtein é uma distância métrica, mas NormalizedLevenshtein não é.
Muitos algoritmos de busca do vizinho mais próximo e estruturas de indexação dependem da desigualdade triangular. Você pode verificar "Similarity Search, The Metric Space Approach" de Zezula et al. para uma pesquisa. Estes não podem ser usados com medidas de similaridade não métricas.
Leia Javadoc para uma descrição detalhada
Alguns algoritmos funcionam convertendo strings em conjuntos de n-gramas (sequências de n caracteres, às vezes também chamadas de k-shingles). A semelhança ou distância entre as cordas é então a semelhança ou distância entre os conjuntos.
Alguns deles, como o jaccard, consideram as cordas como conjuntos de telhas, e não consideram o número de ocorrências de cada telha. Outros, como a similaridade de cossenos, funcionam usando o que às vezes é chamado de perfil das cordas, que leva em consideração o número de ocorrências de cada telha.
Para estes algoritmos, outro caso de uso é possível ao lidar com grandes conjuntos de dados:
A distância Levenshtein entre duas palavras é o número mínimo de edições de um único caractere (inserções, exclusões ou substituições) necessárias para transformar uma palavra em outra.
É uma distância de string métrica. Esta implementação utiliza programação dinâmica (algoritmo Wagner-Fischer), com apenas 2 linhas de dados. O requisito de espaço é, portanto, O(m) e o algoritmo é executado em 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 distância é calculada como a distância de Levenshtein dividida pelo comprimento da corda mais longa. O valor resultante está sempre no intervalo [0,0 1,0] mas não é mais uma métrica!
A similaridade é calculada como 1 - distância 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" ));
}
}Uma implementação de Levenshtein que permite definir diferentes pesos para diferentes substituições de caracteres.
Este algoritmo é geralmente usado para aplicações de reconhecimento óptico de caracteres (OCR). Para OCR, o custo de substituição de P e R é menor que o custo de substituição de P e M, por exemplo, porque do ponto de vista do OCR P é semelhante a R.
Também pode ser usado para correção automática de digitação no teclado. Aqui o custo de substituição de E e R é menor, por exemplo, porque estes estão localizados um ao lado do outro em um teclado AZERTY ou QWERTY. Portanto, a probabilidade de o usuário ter digitado incorretamente os caracteres é maior.
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" ));
}
}Semelhante a Levenshtein, a distância Damerau-Levenshtein com transposição (às vezes também chamada de distância Damerau-Levenshtein irrestrita) é o número mínimo de operações necessárias para transformar uma string em outra, onde uma operação é definida como uma inserção, exclusão ou substituição de um único caractere ou uma transposição de dois caracteres adjacentes .
Respeita a desigualdade triangular e, portanto, é uma distância métrica.
Isso não deve ser confundido com a distância ideal de alinhamento da string, que é uma extensão onde nenhuma substring pode ser editada mais de uma 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" ));
}
}Produzirá:
1.0
2.0
1.0
1.0
1.0
6.0
A variante Optimal String Alignment de Damerau-Levenshtein (às vezes chamada de distância de edição restrita) calcula o número de operações de edição necessárias para tornar as strings iguais sob a condição de que nenhuma substring seja editada mais de uma vez , enquanto o verdadeiro Damerau-Levenshtein não apresenta tal restrição. A diferença do algoritmo para distância de Levenshtein é a adição de uma recorrência para as operações de transposição.
Observe que para a distância ideal de alinhamento da string, a desigualdade triangular não é válida e, portanto, não é uma métrica verdadeira.
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" ));;
}
}Produzirá:
3.0
Jaro-Winkler é uma distância de edição de string que foi desenvolvida na área de ligação de registros (detecção de duplicatas) (Winkler, 1990). A métrica de distância Jaro-Winkler foi projetada e mais adequada para sequências curtas, como nomes de pessoas, e para detectar erros de digitação de transposição.
Jaro-Winkler calcula a semelhança entre 2 strings e o valor retornado está no intervalo [0,0, 1,0]. É (aproximadamente) uma variação de Damerau-Levenshtein, onde a transposição de 2 caracteres próximos é considerada menos importante do que a transposição de 2 caracteres distantes um do outro. Jaro-Winkler penaliza acréscimos ou substituições que não podem ser expressos como transposições.
A distância é calculada como 1 - similaridade 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" ));
}
}produzirá:
0.9740740656852722
0.8962963223457336
O problema da maior subsequência comum (LCS) consiste em encontrar a maior subsequência comum a duas (ou mais) sequências. É diferente dos problemas de localização de substrings comuns: ao contrário das substrings, as subsequências não são obrigadas a ocupar posições consecutivas nas sequências originais.
É usado pelo utilitário diff, pelo Git para reconciliar múltiplas alterações, etc.
A distância LCS entre as strings X (de comprimento n) e Y (de comprimento m) é n + m - 2 |LCS(X, Y)| min = 0 máx = n + m
A distância LCS é equivalente à distância de Levenshtein quando apenas a inserção e exclusão são permitidas (sem substituição), ou quando o custo da substituição é o dobro do custo de uma inserção ou exclusão.
Esta classe implementa a abordagem de programação dinâmica, que possui um requisito de espaço O(mn) e um custo de computação O(mn).
Em "Comprimento de Subsequências Comuns Máximas", KS Larsen propôs um algoritmo que calcula o comprimento de LCS no tempo O(log(m).log(n)). Mas o algoritmo tem um requisito de memória O(m.n²) e, portanto, não foi implementado aqui.
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 distância baseada na maior subsequência comum, das notas "Uma métrica de string baseada em LCS" de Daniel Bakkelund. http://heim.ifi.uio.no/~danielry/StringMetric.pdf
A distância é calculada 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" ));
}
}Distância N-Gram normalizada conforme definido por 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
O algoritmo usa afixação com caractere especial 'n' para aumentar o peso dos primeiros caracteres. A normalização é obtida dividindo a pontuação total de similaridade pelo comprimento original da palavra mais longa.
No artigo, Kondrak também define uma medida de similaridade, que (ainda) não está implementada.
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 ));
}
}Alguns algoritmos funcionam convertendo strings em conjuntos de n-gramas (sequências de n caracteres, às vezes também chamadas de k-shingles). A semelhança ou distância entre as cordas é então a semelhança ou distância entre os conjuntos.
O custo para calcular essas semelhanças e distâncias é dominado principalmente pelo k-shingling (convertendo as strings em sequências de k caracteres). Portanto, normalmente existem dois casos de uso para esses algoritmos:
Calcule diretamente a distância entre as strings:
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, para grandes conjuntos de dados, pré-calcule o perfil de todas as strings. A similaridade pode então ser calculada entre perfis:
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 atenção, isso só funciona se o mesmo objeto KShingling for usado para analisar todas as strings de entrada!
Distância Q-grama, conforme definido por Ukkonen em "Correspondência aproximada de strings com q-gramas e correspondências máximas" http://www.sciencedirect.com/science/article/pii/0304397592901434
A distância entre duas strings é definida como a norma L1 da diferença de seus perfis (o número de ocorrências de cada n-grama): SUM( |V1_i - V2_i| ). A distância Q-grama é um limite inferior na distância de Levenshtein, mas pode ser calculada em O(m + n), onde Levenshtein requer O(mn)
A semelhança entre as duas strings é o cosseno do ângulo entre a representação desses dois vetores e é calculada como V1. V2 / (|V1| * |V2|)
A distância é calculada como 1 - similaridade de cosseno.
Assim como a distância Q-Gram, as strings de entrada são primeiro convertidas em conjuntos de n-gramas (sequências de n caracteres, também chamadas de k-shingles), mas desta vez a cardinalidade de cada n-grama não é levada em consideração. Cada string de entrada é simplesmente um conjunto de n-gramas. O índice Jaccard é então calculado como |V1 inter V2| / |União V1 V2|.
A distância é calculada como 1 - similaridade. O índice Jaccard é uma distância métrica.
Semelhante ao índice de Jaccard, mas desta vez a similaridade é calculada como 2 * |V1 inter V2| / (|V1| + |V2|).
A distância é calculada como 1 - similaridade.
Ratcliff/Obershelp Pattern Recognition, também conhecido como Gestalt Pattern Matching, é um algoritmo de correspondência de strings para determinar a similaridade de duas strings. Foi desenvolvido em 1983 por John W. Ratcliff e John A. Obershelp e publicado no Dr. Dobb's Journal em julho de 1988.
Ratcliff/Obershelp calcula a semelhança entre 2 strings e o valor retornado está no intervalo [0,0, 1,0].
A distância é calculada como 1 - similaridade 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" ));
}
}produzirá:
0.8888888888888888
0.7777777777777778
SIFT4 é um algoritmo de distância de string de uso geral inspirado em JaroWinkler e Longest Common Subsequence. Ele foi desenvolvido para produzir uma medida de distância que corresponda o mais próximo possível à percepção humana da distância das cordas. Portanto, leva em consideração elementos como substituição de caracteres, distância de caracteres, maior subsequência comum, etc. Foi desenvolvido por meio de testes experimentais e sem fundamentação teórica.
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);
}
}
Use java-string-similarity em seu projeto e deseja que ela seja mencionada aqui? Não hesite em me deixar uma mensagem!
