note 70824 deleted from function.levenshtein by salathe
| From: | salathe@php.net | Date: | Mon, 18 Nov 2013 09:02:44 +0000 |
| Subject: | note 70824 deleted from function.levenshtein by salathe | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-197550@lists.php.net to get a copy of this message | ||
Note Submitter: ivo_gelov at gmx dot net
----
Here is a small function to implement a fuzzy search.
If someone is wondering about the mathematics inside, this information can be found in "A fast
bit-vector algorithm for approximate string matching based on dynamic programming" by Gene
Myers, May 27 1998
<?php
// This can search for PATTERN into HAYSTACK with MIST mistaken symbols in PATTERN
// OK_MATCH is a function ($Position, $Score)
// Position is zero-based index in HAYSTACK, where PATTERN is found,
// and Score is the number of mistaken symbols
function FuzzyLook($pattern,$haystack,$mist,$ok_match)
{
$m = strlen($pattern);
$n = strlen($haystack);
if($n==0 OR $m==0) return;
// Precompute Peq[Z]
for($i=0; $i<32; $i++) $Bit[$i] = (1 << $i);
for($i=0; $i<$m; $i++) $Peq[ ord(substr($pattern,$i,1)) ] |= $Bit[$i];
$Pv = 0xFFFFFFFF;
$Mv = 0;
$Score = $m;
for($j=0; $j<$n; $j++)
{
$Eq = $Peq[ ord(substr($haystack,$j,1))];
$Xv = $Eq | $Mv;
$Xh = ((($Eq & $Pv) + $Pv) ^ $Pv) | $Eq;
$Ph = $Mv | ~ ($Xh | $Pv);
$Mh = $Pv & $Xh;
if($Ph & (1 << ($m-1))) $Score += 1;
elseif($Mh & (1 << ($m-1))) $Score -= 1;
$Ph <<= 1;
$Pv = ($Mh << 1) | ~ ($Xv | $Ph);
$Mv = $Ph & $Xv;
if($Score <= $mist && $j>=$m-1) $ok_match($j-$m+1,$Score);
}
}
?>