Olá amigos, tudo bem? Sejam bem vindos ao terceiro e último de meus artigos sobre a Distância Levenstein.

Nesta última etapa irei cumprir minha promessa de deixar tudo um pouco  mais complicado, então lhe recomendo fortemente ler as partes 1 e parte 2 caso você ainda não tenha feito isso.

Analisando novamente as palavras Bela e Bola

Em nossa análise inicial, chegamos no ponto onde a comparação das palavras “BELA”  e “BOLA” resultou na tabela x demonstrada abaixo:

O nosso próximo passo será o de realizar um “passeio” entre todas as células dessa tabela, utilizando 2 indices i e j (conforme detalhei em meu segundo artigo) e em cada célula aplicar o seguinte algoritmo proposto por Levensthein in 1965.

As duas hipóteses de Max (i, j) e Min (i,j) = 0 demonstradas na fórmula já foram abordadas no primeiro artigo, logo a primeira linha dentro das chaves será ignorada.

Podemos então submeter as 3 operações restantes nas outras células não preenchidas de nossa tabela:

Operação 1

Obter o valor  x(i – 1, j) e somar mais 1 unidade.

Celula x(i -1, j) assumindo que x =1 e y = 1 uma vez que as células com letras não entram na contagem.

Como pode ser observado, o valor da célula x(i-1 , j) é igual a 2. Prosseguimos para próxima etapa.

Operação 2

Obter o valor x (i, j – 1) e somar mais 1 unidade.

Célula (i, j -1) seguindo o mesmo princípio mostrado acima.

Como pode ser observado, o valor da célula x(i, j-1) também é igual a 2.

Antes de avançarmos para terceira operação, preciso fazer uma ressalva:

Até agora estávamos ocupando a primeira linha e a primeira coluna de forma incremental até formar toda a palavra. Este raciocínio foi importante para a primeira parte de nossa análise.

Contudo, para entendermos a terceira operação será necessário abstrair dessa ideia e exibir a tabela analisando letra a letra como demonstrado abaixo.

Operação 3

Na operação 3, iremos obter o valor de x(i -1, j -1) e somar 1. Porém esta soma de +1 só irá acontecer se o valor de x(i -1, j)  for diferente do valor de x(i, j-1).

Caso contrário, o valor  a ser considerado na operação será o de x(i -1, j -1).

Em nosso caso, como não será feita essa soma (pois tanto x(i -1, j) quando x(i, j -1)  fazem referência à letra B), o resultado da Operação 3 será zero.

Operação 3 resultando em 0.

Cálculo do mínimo

Depois de  realizarmos as 3 operações, vem o passo final: escolher o menor dos resultados e colocar em x(i,j).

Como a nossa terceira operação resultou em zero, escolheremos este valor pois ele é o mínimo.

E seguindo este pensamento, ficou intuitivo deduzir todo o resto da tabela. (Recomendo realizar numa folha de papel para melhor entendimento)

O último valor em diagonal, que corresponde a última posição x[i,i] é o valor buscamos de distância entre as duas palavras : 1.

Conclusão

Utilizei um exemplo bastante simples para deixar a explicação o mais didática possível. Prever que a distância de caracteres entre as palavras Bola/Bela terá apenas uma unidade, é algo bastante intuitivo e trivial.

Nesse caso é muito mais complicado inferir visualmente

Mas quando as palavras envolvidas tem uma grande quantidade de caracteres a análise deixa de se tão simples e é aí que o nosso algoritmo em análise é tão poderoso.

Ao longo de meus estudos percebi com muito fascínio que a estratégia de utilizar tabelas auxiliares para resolver um problema complexo é um recurso bastante comum na Ciência da Computação.

Caso também tenha ficado intrigado com essa técnica, fique a vontade para comentar a respeito, pois pretendo em breve me aprofundar no assunto Programação dinâmica nos próximos artigos.

Obrigado pela leitura e um grande abraço.