Strings are ubiquitous and ambiguous. When a communication channel is established, an inevitable noise and misunderstandings can introduce errors in the transfer of textual data.
In an enterprise system, there are many places where this type of error can occur. Customer names, addresses, company names, among others. This type of error may make it impractical to query for a record. Imagine the sad life of our famous actor Arnold Schwarzenegger action movies, how many times he had to spell his name for the operator?
To resolve this problem, some algorithms were created to search for words closer together, and among them are phonetic algorithms. An algorithm uses phonetic rules to transform strings into phonemes, trying to unify it with similar-sounding words. Examples of algorithms:
But all these algorithms suffer from the same problems. The rules are written specifically for a particular language, and most implementations have English as target language. This is not a problem if your system is for English speaking users and you are not interested in making applications in various languages ... Because this world is increasingly globalized, I find it very hard to be the case ...
But there are other solutions? Good news! Looking for alternatives, I thought of words to search algorithms approximate the edit distance category, especially the Levenshtein distance algorithm . More robust and reliable, can be used by any programmer in any language without change. And even with a small advantage: it not only returns a Boolean response, saying it was successful or not in the search, but a number that tells how similar are two words, which makes it possible to sort a collection of candidates for its distance from the floor requested. This small advantage can be the difference between pages and pages of results without value, or an ordered list with the most relevant results first.
The algorithm of Levenshtein distance, which is named after its creator, the Russian Vladimir Levenshtein , calculates the cost of transforming one word into another, assuming some operations such as insert, remove or replace a character. Can be described as follows:
Be yourself and sj strings of characters i, j integers such that 0 <= i <= size (self) and 0 <= j <= size (j). Is d (bs, sj) function that calculates the edit distance between itself and sj.
A length (si) is equal to 0, then d (bs, sj) = length (sj). The converse holds for sj.
If you and sj are not empty strings, then can be written as si = sj = sj'c2 si'c1 and, where c1 is the last character of himself, and c2 is the last character of sj. So it goes:
If c1 = c2, then obviously d (si, sj) = d (si, 'sj').
If c1! = C2, then d (bs, sj) = min (1 + d (bs ', sj'c2), 1 + d (si'c1, sj "), 1 + d (bs', sj") ) = 1 + (minimum d (bs ', sj'c2), d (si'c1, sj "), d (bs', sj"))
The last line deserves an explanation. If C1 is different from c2, then the edit distance between itself and sj is the smallest number of operations that do is remove itself c1, c2 or removed SJ, we believe that we replace or C1 to C2 (or vice versa .)
As you can see, this gives us a beautiful recursive algorithm that can be written in Java as well:
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!
