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 que será usado como base para sugerir as palavras corretas.

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));
?>

Depois de criado o arquivo com o dicionário em formato de um array serializado, é só escolher um dos algoritmos a seguir, considerando que o primeiro é mais simples e o segundo é mais rápido:

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 caracter
• 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;
}
?>

2 – Algoritmo de Peter Norvig

Toda explicação probabilística desse algoritmo 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 o implementa e disponibilizei sob Licença BSD no PHPClasses.org (http://www.phpclasses.org/browse/package/4859.html).