Recentemente precisei implementar um sistema de correção ortográfica à la Google.
Pesquisei bastante sobre como fazer isso, e encontrei duas maneiras que explicarei agora, mas antes disso explicarei algo que é comum às duas: A criação do dicionário
Para criar o dicionário, você precisa ter uma base de palavras, que idealmente é um arquivo txt.
Você lê o arquivo e cria um array onde as palavras são as chaves e as frequências com que aparecem nos textos serão os valores.
<?php
$text = file_get_contents(‘arquivo.txt’);
preg_match_all(“/[a-z]+/”,strtolower($text),$matches);
$palavras = $matches[0];
$dicionario = array();
foreach($palavras as $palavra)
$dicionario[$palavra] += 1;
sort($dicionario); /* Essa ordenação será útil para otimização de performance no primeiro algoritmo */ file_put_contents(‘dicionario_serializado.dat’,serialize($dicionario);
?>
1 - Algoritmo de Levenshtein
PHP implementa nativamente o algoritmo de Levenshtein (http://php.net/levenshtein), que calcula a distância de edição entre duas palavras, funcionando da seguinte forma:
- suponha que eu tenha duas palavras: água e mágua - A distância de edição delas é de uma inserção de carácter
- suponha que eu tenha as palavras: casa e caixa - A distância delas é de uma substituição (s por i) e uma inserção (x)
- suponha que eu tenha as palavras: arrocho e arroto - A distância delas é de uma substituição e uma remoção.
A função levenshtein também permite que você dê pesos diferenciados para inserção/remoção/substituição, sendo que o valor default é 1 para todas operações. Usando essa função, fica simples implementar um corretor, supondo que você tem um dicionário que já citei, você só precisa fazer:
<?php
function voce_quis_dizer($palavra_procurada) {
$dicionario = unserialize(file_get_contents(‘dicionario_serializado.dat’)); $minima_distancia = -1;
$palavra_procurada = strtolower($palavra_procurada);
foreach($dicionario as $palavra_do_dicionario) {
if($palavra_procurada == $palavra_do_dicionario) return $palavra;
$distancia = levenshtein($palavra_procurada,$palavra_do_dicionario);
if($distancia < $minima_distancia || $minima_distancia == -1) {
$minima_distancia = $distancia;
$sugestao = $palavra_do_dicionario;
}
}
return $sugestao;
}
?>
Análise de desempenho:
Considerando que temos k palavras no dicionário, a palavra que desejamos procurar tem m letras e cada palavra do dicionário tem em média n letras, o algoritmo de Levenshtein tem ordem de complexidade O(m*n) onde para k comparações (no caso da palavra não existir no dicionário, já que se ela existir não teremos nenhuma comparação) teremos O(k*m*n) (k*m*n operações onde k é muito maior que m e n).
2 - Algoritmo de Peter Norvig
Toda explicação probabilística desse algorítmo está presente no site do Norvig, um cara renomado na área de inteligência artificial: http://norvig.com/spell-correct.html. Mas basicamente esse algoritmo apesar de mais complicado é bem mais inteligente que o primeiro. O que ele faz é o seguinte: gera perturbações na sua palavra procurada e vê quais dessas perturbações é a mais relevante no dicionário. Evitando comparações desnecessárias, já que no primeiro algoritmo cada palavra que você colocar será comparada com todas as outras (por exemplo: se você digitar BOLA, e ela não existir no dicionário ela será comparada com palavras absurdas como: LIVRO, que obviamente não é o que você quis dizer).
Apesar do conceito do Norvig ser simples, o código é um pouquinho complicado. Então eu criei uma classe que implementa ele e disponibilizei sob Licença BSD no PHPClasses.org (http://www.phpclasses.org/browse/file/24605.html) e tenho recebido elogios e feedback muito positivo de quem está usando.
Análise de desempenho:
Considerando 26 letras do alfabeto (depois da reforma da língua portuguesa, agora também temos 26 letras! :D) e considerando que sua palavra tem m letras, teremos mais ou menos 26*m iterações para gerar as possíveis perturbações na palavra (inserções, remoções e substituições possíveis), e para garantir um segundo nível de perturbações teremos aproximadamente 26*m para cada perturbação gerada, que dá um total de aproximadamente (26*m)*(26*m) = 676 m². Agora só precisamos consultar cada uma das perturbações para vermos qual a mais relevante no dicionário. Cada consulta no dicionário é O(1) então desprezaremos na análise de performance.
E podemos considerar esse algoritmo como sendo mais eficiente do que o primeiro pois o tempo de execução cresce de acordo com o quadrado do tamanho da palavra (que normalmente é bem menor do que o tamanho do dicionário). Enquanto o primeiro sofre interferência do tamanho do dicionário e do tamanho médio das palavras contidas lá, então esse é bem mais inteligente e eficiente.
Espero ter ajudado!
Você tem medo de REGEX!? Eu também!
Com o aumento da complexidade de recursos dos sites na Web, o termo Webmaster entra cada vez mais em extinção.
Aqui vai um endereço que talvez possa lhe ajudar: 
