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:

• Soundex
• Daitch-Mokotoff Soundex
• Metaphone
• Double Metaphone

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.

Finalmente terminei meu TCC em Gerenciamento de Projetos para o curso de gerenciamento de projetos da FGV. Meu grande erro foi deixar para a última hora, e o que era pra ser uma remédio amargo em dose homeopática, foi um tratamento intensivo e doloroso.

E eu gosto de escrever, nada contra. Mas escrever um trabalho acadêmico envolve uma série de tecnicalidades que não são nada divertidas, como seguir a norma ABNT para trabalhos acadêmicos. Só tenho o que agradecer ao LaTeX e o pessoal do abnTex. Amigos, vocês são demais e foram a minha salvação. Se eu tivesse que me preocupar com estes detalhes, ainda estava na décima página do meu trabalho!

Mas deixando as coisas técnicas de lado, fiquei feliz com o resultado. Recolher tantas fontes de informação e tentar criar um texto coeso não é das tarefas mais fáceis. Não que eu tenha conseguido, mas fiquei feliz até onde consegui chegar…

Meu TCC tenta determinar a relação entre as boas práticas descritas no PMBOK do PMI e as metodologias ágeis. Hoje existe muito material na rede tratando o mesmo assunto, uns dizendo que dá pra levar um projeto ágil de acordo com o PMBOK, outros dizendo que não, e eu resolvi acabar com a polêmica de uma vez por todas. E aí está!

Curioso? Ok, não vou obrigar você a ler todo o meu trabalho… Na minha humilde opinião, o que acontece hoje é um choque entre dois paradigmas (adoro essa palavra…), onde o PMBOK traduz a soma de todo conhecimento em gerenciamento de projetos em milhares de anos de projetos…. convencionais! Todos os outros tipos de projeto apontavam para um tipo de solução, passível de planejamento, bem comportada… mas o software é diferente, intangível, complicado, envolve técnica, gênio e arte… E assim surge o conflito: como assim esse tal de software vem e desafia milhares de anos de acúmulo de conhecimento na área?

E todo o mercado que é criado a volta de padrões estabelecidos… fica muito mais difícil estabeler padrões num alvo móvel como as metodologias de desenvolvimento de software. A verdade é que ainda temos muito o que aprender sobre desenvolvimento de software, e temos que caminhar rápidos e leves. O peso de padrões e certificados atrapalham a caminhada.

A maior arma que podemos ter neste mundo de mudanças cada vez mais rápidas é a reflexão. Qual a melhor metodologia a ser seguida? Não sei se existe uma pronta, mas aprenda algumas e reflita sobre. As práticas do PMBOK servem para o seu mais novo projeto? Pense sobre os detalhes e reflita. A velocidade das mudanças nos faz cair na armadilha das soluções prontas, que nos faz na verdade perder muito mais tempo.

Reflita sobre o que disse.