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:
| ” | B | BO | BOL | BOLA | |
| ” | 0 | 1 | 2 | 3 | 4 |
| B | 1 | ||||
| BE | 2 | ||||
| BEL | 3 | ||||
| BELA | 4 |
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.
| ” | B | O | L | A | |
| ” | 0 | 1 | 2 | 3 | 4 |
| B | 1 | ||||
| E | 2 | ||||
| L | 3 | ||||
| A | 4 |
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.
| ” | B | O | L | A | |
| ” | 0 | 1 | 2 | 3 | 4 |
| B | 1 | 0 | |||
| E | 2 | ||||
| L | 3 | ||||
| A | 4 |
E seguindo este pensamento, ficou intuitivo deduzir todo o resto da tabela. (Recomendo realizar numa folha de papel para melhor entendimento)
| ” | B | O | L | A | |
| ” | 0 | 1 | 2 | 3 | 4 |
| B | 1 | 0 | 1 | 2 | 3 |
| E | 2 | 1 | 1 | 2 | 3 |
| L | 3 | 2 | 2 | 1 | 2 |
| A | 4 | 3 | 3 | 2 | 1 |
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.
