note 63274 added to function.levenshtein
| From: | dineshATdinsoftDOTnet at osu1 dot php dot net | Date: | Fri, 17 Mar 2006 23:18:15 +0000 |
| Subject: | note 63274 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-106006@lists.php.net to get a copy of this message | ||
Here is a string resynch function:
<?php
// Trouve les operations a effectuer pour modifier $b en $a en exploitant leurs similitudes (Finds
the operations required to change $b to $a)
// Identique a la fonction Resynch Compare de Hex Workshop
//
// Parametres:
// $a Premiere chaine (cible, target)
// $b Seconde chaine (source)
// $l Nombre d'octets devant correspondre pour etre consides comme un bloc similaire
(number of matching bytes required)
// $s Distance maximale dans laquelle les blocs similaires sont cherches (search window)
//
// Retourne:
// Array
// Array
// [0] Operation: + Add , - Del , / Replace, = Match
// [1] Source offset
// [2] Source count
// [3] Target offset
// [4] Target count
//
function str_resynch($a,$b,$l=32,$s=2048) {
$r=array();
for($i=0,$c=strlen($a),$cc=strlen($b),$ii=0,$z=$s-1,$z2=($z<<1)+1; $i<$c; $i++) {
$d=$i-$z;
$d=($d<$ii)?substr($b,$ii,$z2-$ii+$d):substr($b,$d,$z2);
$p=strpos($d,$a{$i});
$n=0;
while ($p!==FALSE) {
$m=1;
$bi=$i;
$bp=$p;
$p+=$ii;
while ((++$i<$c) && (++$p<$cc)) {
if ($a{$i}!=$b{$p}) break;
$m++;
}
if ($m<$l) {
$i=$bi;
$n=$bp+1;
$p=@strpos($d,$a{$i},$n);
}
else {
$i--;
$r[]=array($bi,$bp+$ii,$m); // offset a, offset b, Count
$ii=$p;
break;
}
}
}
if (!count($r)) return
($cc)?array('/',0,$c,0,$cc):array(array('+',0,$c,0,0));
$o=array();
$bi=0;
$bp=0;
for($i=0,$m=count($r);$i<$m;$i++) {
if ($r[$i][0]!=$bi) {
if ($r[$i][1]!=$bp) {
// Replace
$o[]=array('/',$bi,$r[$i][0]-$bi,$bp,$r[$i][1]-$bp);
$bi=$r[$i][0];
$bp=$r[$i][1];
}
else {
// Insertion
$o[]=array('+',$bi,$r[$i][0]-$bi,$bp,0);
$bi=$r[$i][0];
}
}
elseif ($r[$i][1]!=$bp) {
// Delete
$o[]=array('-',$bi,0,$bp,$r[$i][1]-$bp);
$bp=$r[$i][1];
}
// Match
$o[]=array('=',$r[$i][0],$r[$i][2],$r[$i][1],$r[$i][2]);
$bi+=$r[$i][2];
$bp+=$r[$i][2];
}
if ($c!=$bi) {
if ($cc!=$bp) $o[]=array('/',$bi,$c-$bi,$bp,$cc-$bp);
else $o[]=array('+',$bi,$c-$bi,$bp,0);
}
elseif ($cc!=$bp) $o[]=array('-',$bi,0,$bp,$cc-$bp);
return $o;
}
?>
----
Server IP: 194.153.94.11
Probable Submitter: 84.74.72.172
----
X-Spam-Status: No, hits=3.1 required=5.0 tests=DATE_MISSING,FROM_NO_LOWER
autolearn=no version=2.64
----
Manual Page -- http://www.php.net/manual/en/function.levenshtein.php
Edit -- http://master.php.net/note/edit/63274
Del: integrated -- http://master.php.net/note/delete/63274/integrated
Del: useless -- http://master.php.net/note/delete/63274/useless
Del: bad code -- http://master.php.net/note/delete/63274/bad+code
Del: spam -- http://master.php.net/note/delete/63274/spam
Del: non-english -- http://master.php.net/note/delete/63274/non-english
Del: in docs -- http://master.php.net/note/delete/63274/in+docs
Del: other reasons-- http://master.php.net/note/delete/63274
Reject -- http://master.php.net/note/reject/63274
Search -- http://master.php.net/manage/user-notes.php