[Resolvido] Erro em algoritmo de busca aproximada

[tigredonorte 1]

Bem, estou tentando implementar o algoritmo shift and aproximado em php. Acredito que seja possível, uma vez que a linguagem oferece os operadores logicos necessários.

 

O problema é que o algoritmo nao encontra as palavras corretamente, alguem sabe onde está o erro?

algoritmo:

 

 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;

       $Masc[$MAXCHAR];
       $R[$NUMMAXERROS];
       for ($i = 0; $i < $MAXCHAR; $i++) $Masc[$i] = 0;

       for ($i = 1; $i <= $m; $i++) {$Masc[$Padrao[$i-1] + 127] |= 1 << ($m - $i); }

       $R[0] = 0;
       $Ri = 1 << ($m - 1);

       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[$Texto[$i] + 127];
           $R[0] = $Rnovo;
           for ($j = 1; $j <= $num_erros; $j++)
           {
               $Rnovo = ((($R[$j]) >> 1) & $Masc[$Texto[$i] + 127]) | $Rant | ((($Rant | $Rnovo)) >> 1);
               $Rant = $R[$j];
               $R[$j] = $Rnovo | $Ri;
           }
           if (($Rnovo & 1) != 0)
           echo(" Casamento na posicao ". ($i + 1) . "<br />");
       }
   }

$Texto = "Loremffdfdfasdfasdf sal";
$Palavra = "kikos sab";

ShiftAndAproximado($Texto, $Palavra, 1);

 

Se alguém puder me ajudar, agradeço

[João Batista Neto 448]

Dê uma olhada nessas duas funções:

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif levenshtein()

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif gmp_hamdist()

[tigredonorte 1]

Dê uma olhada nessas duas funções:

 

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif levenshtein()

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif gmp_hamdist()

 

Bom.. a primeira funçao eu já conhecia, e tenho até um algoritmo para casamento exato de palavras usando ela, ou seja, usando a distância de leveinstein. A segunda função não funcionou no meu servidor, de forma que para o meu caso ela não serve.

 

A vantagem de usar o shift and aproximado é que ele é em tese mais eficiente do que o outro algoritmo que tenho, eu fiz uma implementação dele em C, que me atende superbem. A outra vantagem dele, é que não preciso dividir uma string em partes, pois o proprio algoritmo já faz isto por mim. Quanto ao erro no algoritmo que eu postei acima pode ser que ocorra pelo fato que nas linhas a seguir eu preciso de um inteiro sem sinal (unsigned long) mas o php não suporta unsigned pelo que pesquisei...

 

trechos que deveriam ser unsigned:

 

$Rnovo = (((unsigned long)($Rant) >> 1) | $Ri) & $Masc[$Texto[$i] + 127]; 

$Rnovo = ((((unsigned long)$R[$j]) >> 1) & $Masc[$Texto[$i] + 127]) | $Rant | (((unsigned long)($Rant | $Rnovo)) >> 1);

 

 

talvez se tiver uma forma de obrigar o php a tratar estas partes como unsigned eu consiga implementar o algoritmo. Alguma sugestão?

[Henrique Barcelos 290]

Ao que parece, o PHP não tem suporte a números sem sinal:

PHP does not support unsigned integers. Integer size can be determined using the constant PHP_INT_SIZE, and maximum value using the constant PHP_INT_MAX since PHP 4.4.0 and PHP 5.0.5.

http://forum.imasters.com.br/public/style_emoticons/default/seta.gif http://php.net/manual/en/language.types.integer.php

[tigredonorte 1]

Realmente segundo esta página não tem, mas encontrei no fórum uma forma de imprimir uma número desconsiderando o sinal, o problema é que ele não converte o número ou algo do tipo, ele apenas imprime na tela, talvez tenha alguma forma de fazer com que este número seja 'transformado'.

Veja o link

[tigredonorte 1]

Bom galera, consegui resolver o problema.. Era bem simples... em uma parte do algoritmo, onde em c eu faço um cast em uma string para pegar seu valor numerico, acontece que em php nao existe tal cast, mas existe uma funcao que transforma o valor em numerico e assim deu pra resolver.

 

Se alguém tiver interesse em utilizar a solução, ela foi postada no fórum: Busca Aproximada

 

Problema resolvido!