Em algum dia da sua vida você possivelmente digitou alguma palavra de forma incorreta e foi educadamente corrigido por um software. O Editor de Texto Microsoft Word, por exemplo, marcou a gramática de muita gente com este recurso.

Contudo, você já parou para imaginar qual é a lógica existente nesse processo de correção gramatical?

Irei lhe apresentar, neste e em outros artigos, um algoritmo que mede de forma bastante engenhosa a similaridade entre duas palavras e que, por consequência, também é utilizado em outros  campos do conhecimento como Análise de DNA,  Inspeção de Direitos Autorais e até mesmo Identificação de discurso de ódio em Redes Sociais.

 

Conceito Inicial

Em 1965 um Matemático Russo chamado Vladimir Levenshtein apresentou ao mundo um conceito chamado de Distância Levenshtein, que calcula, através de um conjunto de regras, se duas palavras são similares ou não.

Em suma, o algoritmo criado por esse famoso cientista monitora a utilização de 3 tipos básicos de operações de edição (inserção, remoção e substituição).

A quantidade de vezes que essas operações precisam ser utilizadas para igualar duas palavras é entendida como a distância entre elas.

Desse modo, a técnica inventada pelo Russo recebeu duas nominações distintas: alguns a chamam de Distância de Levenshtein e outros de Distância de Edição.

Para um melhor entendimento, veja os exemplos abaixo:

• Para igualar a palavra Bola com a palavra Bela é necessário realizar uma operação de substituição (substituir a letra o pela e). Logo a distância entre as duas é 1.
• Para igualar a palavra Novo com a palavra Nosso é necessário realizar 2 operações (substituir a letra v por s e inserir a letra s mais uma vez). Logo a distância entre as duas  é 2.
• Para igualar a palavra Todos com a palavra Todo é necessário realizar uma operação de remoção (a letra s no final). Logo a distância entre elas é 1.

Contudo, se pra nós humanos a atividade de identificar a distância entre palavras pequenas como Nosso, Novo, Bela e Bola é trivial,  ensinar computadores a fazer o mesmo trabalho pode ser um pouco mais trabalhoso.

 

Complicando as coisas

Em princípio é importante definir que uma letra vazia e sem nenhum caractere (sinalizada aqui por duas aspas simples) será o ponto de partida para construímos o nosso raciocínio.

No livro Algoritmos , Sanjoy Dasgupta representa esse caractere vazio  com um  sublinhado (_).  Portanto, fique a vontade para substituir as aspas por algum outro caractere especial.

Assim sendo, a  tabela abaixo exibe a distância entre um caractere vazio e fragmentos da palavra Bola.

Caracter	Palavra	Distância
”	”	0
”	B	1
”	BO	2
”	BOL	3
”	BOLA	4

De tal sorte que o comportamento se repete, quando trocarmos a palavra por Bola por Bela. 

Caracter	Palavra	Distância
”	”	0
”	B	1
”	BE	2
”	BEL	3
”	BELA	4

Finalmente, quando colocamos as duas tabelas juntas, temos a seguinte configuração

	”	B	BO	BOL	BOLA
”	0	1	2	3	4
B	1
BE	2
BEL	3
BELA	4

 

Conclusão

Decerto chegamos em um ponto onde a inserção do conceito de Programação Dinâmica se tornou inevitável.

O que torna tudo um pouco mais complexo e eventualmente mais fascinante.

Para ganharmos dinamismo quando formos retomar o assunto na parte 2 eu resumi a última tabela mostrada, para o modelo abaixo (que é o encontrado em diversos livros e que num primeiro contato, parece ser meio confuso).

	”	B	O	L	A
”	0	1	2	3	4
B	1
E	2
L	3
A	4

Eu espero muito que todas as ideias tenham ficado claras para você até o momento. E antes de qualquer coisa já lhe peço para utilizar os comentários na intenção de fazer alguma observação ou dúvida sobre o assunto apresentado .

Te aguardo na próxima parte, na qual irei aprofundar um pouco mais no tema.

Muito obrigado pela leitura e um grande abraço.

 

Referências

• Entendendo Algoritmos – Aditya Y. Bhargava
• Algoritmos – Sanjoy Dasgupta, Christos Papadmitriou, Umesh Vazirani