Há algum tempo, venho listando alguns temas que sempre achei interessante estudar e entender melhor. Entre eles estava o tratamento de strings com PHP. Resolvi então, iniciar esta nova série de postagens para compartilhar algumas funções, que podem ser interessantes tratamento de strings.
Para hoje, explico a função Levenshtein. Apesar de pouco usada e comentada nas redes de discussão, a função Levenshtein tem aplicações que confesso me surpreenderam. Mas, vamos por partes.
Definição da função Levenshtein
A função é responsável por definir a “distância” entre duas strings, baseada na quantidade de alterações que a palavra 1 precisa sofrer para virar uma determinada palavra 2. Neste sistema, são consideradas como alterações: as substituições, remoções e inclusões de caracteres. Ao fim da comparação esta função vai retornar um valor númerico entre 0 e 255, ou -1 se algum dos argumentos for maior que 255 caracteres.
Utilizando a função Levenshtein para tratamento de strings
Ok, acredito que já deu para pelo menos termos uma noção sobre esta função, então vamos para a aplicação. Afinal o que esta função completamente diferente pode fazer por nós, meros mortais? Bem, a primeira aplicação direta que me veio a cabeça foi algo muito utilizado para nos ajudar em buscas e edições de texto. O famoso corretor ortográfico.
A função é responsável por comparar a “distância” entre duas palavras utilizando a quantidade de alterações. Sendo assim, chegamos a conclusão que de que ela analisa a semelhança entre duas palavras. Com um pouco mais de tratamento e algumas condições podemos então retornar sugestões de palavras semelhantes para substituir em seu texto. Ou simplesmente sugerir uma nova busca.
Vamos para o código então?
Para utilizar este comando e conseguir sugestões relevantes, precisaremos buscar palavras a serem comparadas com a palavra que está sendo digitada. Utilizarei um array de palavras, mas o mesmo pode vir de um resultado de banco de dados ou outra fonte de dados.
casino online</a> true"><?php
if($_GET){
$input = $_GET[word];
// Array de palavras
$words = array('DialHost','Hospedagem','Sites','Cloud',
'Computing','Servidores','Brasil','iMasters','PHP');
A partir de agora inicio minha busca dentro do array para encontrar uma sugestão de palavra semelhante.
// Inicio uma variável com a menor distância encontrada pela busca
$sht = -1;
// Inicio o loop de comparação das palavras
foreach ($words as $word) {
//Faço a comparação das distâncias entre a palavra digita e a palavra selecionada no array.
$lev = levenshtein($input, $word);
// Verifico se a palavra do array é igual a palavra digitada.
if ($lev == 0) {
// Defino a palavra digitada como sendo a palavra final
$print_word = $word;
$sht = 0;
//Já que a palavra exata já foi encontrada não preciso mais continuar no loop.
break;
}
// Se a palavra do array não for exata começo a comparar se ela é mais próxima que a comparada anteriormente.
if ($lev <= $sht || $sht < 0) {
// Se der verdadeiro a palavra será guardada como a palavra final
$print_word = $word;
// E defino o valor levenshtein da palavra como o mais próximo. Este valor será utilizado nas comparações seguintes.
$sht = $lev;
}
}
?>Por fim criei um html básico para imprimir os resultados da minha busca e o formulário para que eu possa digitar uma nova busca.
<!DOCTYPE html>
<html lang="pt-br">
<head>
<title>Levenshtein</title>
<meta charset="utf-8">
</head>
<body>
<?php
echo "<div style='margin-top:50px;text-align:center;font-family:arial,sans-serif;font-size:1.6em;'>A palavra digitada foi:".$input."</div>";
if ($sht == 0) {
echo "<div style='text-align:center;font-family:arial,sans-serif;font-size:1.6em;'>Encontramos a palavra exata para sua busca:".$print_word."</div>";
} else{
echo "<div style='line-height:1.7em;text-align:center;font-family:arial,sans-serif;font-size:1.6em;'>Talvez você esteja procurando por:".$print_word."</div>";
}
echo "<div style='margin-top:50px;text-align:center;font-family:arial,sans-serif;font-size:1.6em;'><a href='http://devel2.dialhost.com.br/Blog-SandBox/levenshtein.php' title='Fazer outra busca'>Fazer outra busca</a></div>";
}
else {
?>
<div style="margin-top:50px;text-align:center;font-family:arial,sans-serif;font-size:1em;">
<h1>Apenas um teste com Levenshtein</h1>
<form action="levenshtein.php" method="get" accept-charset="utf-8">
<label> Digite a palavra a ser comparada<br><input style="padding:5px;font-size:1.4em;line-height:1.4em;margin-top:5px;"type="text" name="word" placeholder="ex: DialHost" value=""></label>
<input type="submit" name="buscar" value="Buscar">
</form>
<?php
}
?>
</div>
</body>
</html>Veja o exemplo funcionando aqui.
Assim podemos conferir como funciona um sistema básico de sugestão de palavras ou de correção ortográfico.
Apenas para finalizar. Vocês devem estar questionando que no exemplo a validação faz uma busca com baixa relevância, já que, por menor que seja a similaridade da palavra pesquisada, uma delas será adicionada no resultado. Para tratar isto podemos criar regras mais complexas de relevância utilizando strlen(), por exemplo. Mas este comando fica pra um próximo post da série.
Espero que esta dica rápida tenha ajudado no tratamento. Caso queira aprofundar mais sobre este comando, indico o próprio manual do PHP.
