![](https://www.deviante.com.br/wp-content/uploads/2024/07/9-e1722820486414.jpg)
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 i -1](https://i0.wp.com/www.deviante.com.br/wp-content/uploads/2024/07/4.png?resize=300%2C137&ssl=1)
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)](https://i0.wp.com/www.deviante.com.br/wp-content/uploads/2024/07/3.png?resize=300%2C124&ssl=1)
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](https://i0.wp.com/www.deviante.com.br/wp-content/uploads/2024/07/7.png?resize=300%2C115&ssl=1)
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.
![Análise complexa](https://i0.wp.com/miro.medium.com/v2/resize:fit:392/1*VigSVyiXcvoGmNZJh4_gdA.gif?resize=392%2C260&ssl=1)
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.