Le stringhe sono onnipresenti e ambigue. Quando un canale di comunicazione è stabilita, un rumore inevitabile e incomprensioni possibile introdurre errori nel trasferimento dei dati testuali.
In un sistema aziendale, ci sono molti posti dove questo tipo di errore può verificarsi. I nomi dei clienti, indirizzi, nomi di società, tra gli altri. Questo tipo di errore potrebbe rendere impraticabile per eseguire una query per un record. Immaginate la triste vita dei nostri famoso attore Arnold Schwarzenegger film d'azione, quante volte ha dovuto scrivere il suo nome per l'operatore?
Per risolvere questo problema, alcuni algoritmi sono stati creati per cercare le parole più vicini, e tra loro ci sono algoritmi fonetici. Un algoritmo utilizza le regole fonetiche per trasformare le stringhe in fonemi, cercando di unificare con suono simile parole. Esempi di algoritmi:
Ma tutti questi algoritmi soffrono degli stessi problemi. Le regole sono scritte appositamente per una determinata lingua, e la maggior parte delle implementazioni hanno l'inglese come lingua di destinazione. Questo non è un problema se il sistema è per gli utenti di lingua inglese e non siete interessati nella presentazione di domande in varie lingue ... Perché questo mondo è sempre più globalizzato, trovo molto difficile essere il caso ...
Ma ci sono altre soluzioni? Buone notizie! Alla ricerca di alternative, ho pensato di parole per cercare algoritmi approssimare la categoria edit distance, in particolare l'algoritmo di Levenshtein distanza . Più robusto e affidabile, può essere utilizzato da qualsiasi programmatore in qualsiasi lingua senza modifiche. E anche con un piccolo vantaggio: non solo restituisce una risposta booleano, dicendo che era successo o meno nella ricerca, ma un numero che racconta come simili sono due parole, il che rende possibile ordinare una collezione di candidati per la sua la distanza dal pavimento richiesto. Questo piccolo vantaggio può essere la differenza tra le pagine e pagine di risultati senza valore, o un elenco ordinato con i risultati più rilevanti Prima.
L'algoritmo di distanza Levenshtein, che prende il nome dal suo creatore, il russo Vladimir Levenshtein , calcola il costo di trasformare una parola in un altro, assumendo alcune operazioni come inserire, rimuovere o sostituire un carattere. Può essere descritta come segue:
Siate voi stessi e le stringhe di caratteri sj i, j interi tali che 0 <= i <size = (auto) e 0 <= j <size = (j). E 'd (bs, sj) funzione che calcola la distanza tra sé e modifica sj.
A Lunghezza (SI) è uguale a 0, allora d (bs, sj) = lunghezza (sj). Il contrario vale per sj.
Se tu e sj non sono stringhe vuote, allora può essere scritto come si = sj = sj'c2 si'c1 e, se c1 è l'ultimo carattere di se stesso, e c2 è l'ultimo carattere del sj. Così va la vita:
Se c1 = c2, poi, ovviamente, d (si, sj) = d (si, 'sj').
Se c1! = C2, allora d (bs, sj) = min (1 + d (bs ', sj'c2), 1 + d (si'c1, sj "), 1 + d (bs', sj") ) = 1 + (minimo d (bs ', sj'c2), d (si'c1, sj "), d (bs', sj"))
L'ultima riga merita una spiegazione. Se è diverso da C1 C2, allora la distanza tra sé e modifica sj è il più piccolo numero di operazioni che fare è rimuovere se stesso c1, c2 o rimosso SJ, riteniamo di sostituire o da C1 a C2 (o viceversa .)
Come potete vedere, questo ci dà un algoritmo ricorsivo bella che può essere scritto in Java, nonché:
static int levenshtein(String si, String sj) {
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (si.charAt(i) == sj.charAt(j)) {
return d(si, i - 1, sj, j - 1);
}
return 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
Apesar de achar o algoritmo recursivo mais fácil de entender e implementar, infelizmente ele é muito ineficiente. Se acompanhamos a execução para duas cadeias quaisquer, vemos que são calculadas solução para as mesmas subcadeias repetidas vezes. Por exemplo, ao calcular a distância entre as palavras "gente" e "gene" (distância 1), vemos a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre gen e gen
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e ge
Calculando distância entre g e g
Calculando distância entre g e ge
Calculando distância entre g e g
Distancia 1
Relembrando as aulas de algoritmos da faculdade, podemos ver que este algoritmo possue algumas características importantes: substrutura ótima (a solução ótima contêm soluções ótimas para subproblemas), os subproblemas são independentes e o espaço de subproblemas é tão reduzido que o algoritmo recursivo está o tempo todo resolvendo os mesmos problemas. Terreno fértil para o uso de técnicas de programação dinâmica.
Uma das técnicas mais conhecidas é o da memoização. Simplificando, trata-se simplesmente em construir uma tabela com os resultados parciais assim que são calculados, evitando com isso os recalculos desnecessários. Alterando a implementação recursiva anterior utilizando esta técnica, ficaria:
private static int[][] mem;
static int levenshtein(String si, String sj) {
mem = new int[si.length()][sj.length()];
for (int i = 0; i < si.length(); i++) {
for (int j = 0; j < sj.length(); j++) {
mem[i][j] = -1;
}
}
return d(si, si.length() - 1, sj, sj.length() - 1);
}
static int d(String si, int i, String sj, int j) {
if (i == -1) {
return j + 1;
}
if (j == -1) {
return i + 1;
}
if (mem[i][j] > -1) {
return mem[i][j];
}
if (si.charAt(i) == sj.charAt(j)) {
mem[i][j] = d(si, i - 1, sj, j - 1);
return mem[i][j];
}
mem[i][j] = 1 + min(d(si, i - 1, sj, j), d(si, i, sj, j - 1), d(si, i - 1, sj, j - 1));
return mem[i][j];
}
static private int min(int i1, int i2, int i3) {
return Math.min(Math.min(i1, i2), i3);
}
O que nos dá a seguinte pilha de execução:
Calculando distância entre gene e gente
Calculando distância entre gen e gent
Calculando distância entre ge e gent
Calculando distância entre g e gent
Calculando distância entre g e gen
Calculando distância entre g e ge
Calculando distância entre g e g
Calculando distância entre ge e gen
Calculando distância entre ge e ge
Calculando distância entre gen e gen
Distancia 1
Bem melhor que o anterior. Mas infelizmente para quem achava que ia ter esta diversão toda com algoritmos, a triste notícia é que existem excelentes implementações em boas bibliotecas gratuitas, como a implementação de alguns algoritmos fonéticos na Apache Commons Codec , e o Levenshtein no Apache Commons Lang . Com certeza serão implementações bem melhores que as minhas... Mas para um código de brinquedo, já está de bom tamanho!
