Busca aproximada

Bem... vou postar aqui um algoritmo de busca chamado shift and aproximado.

Dado um texto T, um padrao P, e uma tolerancia a erros E, realizar a busca de uma substring do texto T que se aproxime do padrao P por um numero de caracteres de diferenca E.

Este algoritmo foi adaptado do Nivio Ziviani e pode ser encontrado no site: Algoritmos em C

Bem, sem mais delongas, vamos implementar a classe:

/*
* Class: PHPFile
* Autor: Thompson Moreira Filgueiras
* Contato: tigredonorte3@gmail.com
*/
class PHPFile
{
/*
* Função: ShiftAndAproximado
* Algoritmo original em C
* Créditos: Nivio ziviani
* Url: http-~~-//www2.dcc.ufmg.br/livros/algoritmos/cap8/codigo/c/8.1a8.6e8.8-pesquisacadeia.c
Complexidade do algoritmo: O(n E) onde n é o tamanho do texto e E o número de erros
*
* Parâmetros: $texto -> texto fonte, onde será feita a busca pelo padrao
* $Padrao -> string que será procurada no texto
* $num_erros -> Número de letras que pode estar errada ao fazer a busca.
* Caso numerros seje maior do que 10 por exemplo, a maioria das palavras irao casar
* Um valor recomendado é entre 0 e 2, o google faz casamentos de tamanho 1
*
* Resumo: Compara um Texto com uma string Padrao com uma tolerancia num_erros na busca.
* Cria uma máscara de bits onde marca a posição de cada ocorrência de uma letra no texto padrao
* Atravéz de operacoes logicas, shift, and e or compara onde ocorreu casamento de strings
*
* Mais Informações: Projeto de algoritmos e implementações em c e pascal, nívio zivianni
*
* Description: this function search in a $Text some string in argument $padrao. This $padrao can be
* different by text for some error parameter $num_errors. This is a implementation of shiftAndAproach algorithm
*/

 public function ShiftAndAproximado($Texto, $Padrao, $num_erros = 1)
 {
 //recupera tamanho das strings
 $n = strlen($Texto);
 $m = strlen($Padrao);

 //define o maior numero de erros e o maior tamanho da mascara
 $MAXCHAR = 256;
 $NUMMAXERROS = 10;

 //inicializações
 $Masc[$MAXCHAR];
 $R[$NUMMAXERROS];

 //zera a máscara de bits e marca nesta as posicoes onde apareceram determinados caracteres
 for ($i = 0; $i < $MAXCHAR; $i++) $Masc[$i] = 0;
 for ($i = 1; $i <= $m; $i++) {$Masc[ord($Padrao[$i-1]) + 127] |= 1 << ($m - $i);}

 //inivializa r0 com o valor 0
 $R[0] = 0;

 //este valor será constante no resto do algoritmo
 $Ri = 1 << ($m - 1);

 //algoritmo propriamente dito
 for ($j = 1; $j <= $num_erros; $j++) $R[$j] = (1 << ($m - $j)) | $R[$j-1];
 for ($i = 0; $i < $n; $i++)
 {
 $Rant = $R[0];
 $Rnovo = ((($Rant) >> 1) | $Ri) & $Masc[ord($Texto[$i]) + 127];
 $R[0] = $Rnovo;
 for ($j = 1; $j <= $num_erros; $j++)
 {
 $Rnovo = ((($R[$j]) >> 1) & $Masc[ord($Texto[$i]) + 127]) | $Rant | ((($Rant | $Rnovo)) >> 1);
 $Rant = $R[$j];
 $R[$j] = $Rnovo | $Ri;
 }

 //se o ultimo bit é 1, então houve casamento!
 if (($Rnovo & 1) != 0)
 {
 echo(" Casamento na posicao ". ($i + 1) . "<br />");
 }
 }
 }
}

$Texto = "abcdefghijkl Lorem a ipsun ahahahahavcdef abcd";
$Palavra = "abcda";

$phpfile_obj = new PHPFile();
$phpfile_obj->ShiftAndAproximado($Texto, $Padrao, 1);

A idéia de separar esta função em uma classe é complementá-la posteriormente, ao invés de imprimir a posição onde encontrou-se um casamento, podemos retornar esta posição e utilizá-la em algo mais útil do que simplesmente imprimir na tela.