Algoritmos fonéticos versus algoritmos por distância de edição
Strings são ubÃquas e ambÃguas. Quando um canal de comunicação é estabelecido, um inevitável ruÃdo e mal-entendidos podem introduzir erros na transferência de dado textual.
Em um sistema corporativo, há muitos lugares onde este tipo de erro pode ocorrer. Nomes de clientes, endereços, nomes de empresas, entre outros. Este tipo de erro pode tornar impraticável a consulta por um registro. Imagine a triste vida do nosso famoso ator de filmes de ação Arnold Schwarzenegger, quantas vezes ele teve que soletrar seu nome para a telefonista?
Para resolver este tipo de problema, foram criados alguns algoritmos de busca por palavras aproximadas, e entre eles estão os algoritmos fonéticos. Um algoritmo fonético utiliza regras para transformar cadeias de caracteres em fonemas, tentando com isso unificar palavras com sons semelhantes. Alguns exemplos de algoritmos:
Mas todos estes algoritmos sofrem dos mesmos problemas. As regras são escritas especificamente para uma lÃngua em particular, e a maioria das implementações têm como lÃngua alvo o inglês. Este não é um problema se o seu sistema é para usuários falantes da lÃngua inglesa e você não se interessa em fazer aplicações em diversas lÃnguas… Como este mundo está cada vez mais globalizado, eu acho muito difÃcil ser o caso…
Mas existem outras soluções? Boas notÃcias! Procurando por alternativas, achei algoritmos para busca de palavras aproximadas da categoria distância de edição, principalmente o algoritmo da distância de Levenshtein. Mais robusto e confiável, pode ser usado por qualquer programador, em qualquer lÃngua, sem alterações. E ainda com uma pequena vantagem: ele não somente devolve uma resposta booleana, dizendo se houve sucesso ou não na busca, mas sim um número que informa quão semelhantes são duas palavras, o que faz com que seja possÃvel ordenar uma coleção de candidatos pela sua distância em relação a palavra procurada.  Esta pequena vantagem pode ser a diferença entre páginas e páginas de resultados sem valor, ou uma lista ordenada com os resultados mais relevantes primeiro.
O algoritmo da distância de Levenshtein, que recebe o nome de seu criador, o russo Vladimir Levenshtein, calcula o custo de transformar uma palavra em outra, assumindo alguns operações como inserir, remover ou substituir um caracter. Pode ser descrito da seguinte forma:
Sejam si e sj cadeias de carateres e i, j inteiros tais que 0 <= i <= tamanho(si) e 0<= j <= tamanho(j). Seja d(si, sj) a função que calcula a distância de edição entre si e sj.
Se tamanho(si) é igual a 0, então a d(si, sj) = tamanho(sj). O recÃproco vale para sj.
Se si e sj não são cadeias de caracteres vazias, então podem ser escritas como si = si’c1 e sj = sj’c2, onde c1 é o último caractere de si, e c2 é o último caractere de sj. Então vale que:
Se c1 = c2, então obviamente d(si, sj) = d(si’, sj’).
Se c1 != c2, então d(si, sj) = mÃnimo(1 + d(si’, sj’c2), 1 + d(si’c1, sj’), 1 + d(si’, sj’)) = 1 + mÃnimo(d(si’, sj’c2), d(si’c1, sj’), d(si’, sj’))
A última linha merece explicações. Se c1 é diferente de c2, então a distância de edição entre si e sj é o menor número de operações que faremos se removemos c1 de si, ou se removemos c2 de sj, ou então consideramos que substituimos c1 por c2 (ou vice-versa).
Como podemos ver, isso nos dá um belÃssimo algoritmo recursivo que pode ser escrito assim em Java:
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…
Eu espero mostrar como usar o algoritmo de Levenshtein para construir um motor de busca em textos em bancos de dados logo.









