note 24289 added to function.levenshtein
| From: | bisqwit at iki dot fi | Date: | Mon, 12 Aug 2002 11:43:31 +0000 |
| Subject: | note 24289 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-34848@lists.php.net to get a copy of this message | ||
At the time of this manual note the user defined thing
in levenshtein() is not implemented yet. I wanted something
like that, so I wrote my own function. Note that this
doesn't return levenshtein() difference, but instead
an array of operations to transform a string to another.
Please note that the difference finding part (resync)
may be extremely slow on long strings.
<?php
/* matchlen(): returns the length of matching
* substrings at beginning of $a and $b
*/
function matchlen(&$a, &$b)
{
$c=0;
$alen = strlen($a);
$blen = strlen($b);
$d = min($alen, $blen);
while($a[$c] == $b[$c] && $c < $d)
$c++;
return $c;
}
/* Returns a table describing
* the differences of $a and $b */
function calcdiffer($a, $b)
{
$alen = strlen($a);
$blen = strlen($b);
$aptr = 0;
$bptr = 0;
$ops = array();
while($aptr < $alen && $bptr < $blen)
{
$matchlen = matchlen(substr($a, $aptr), substr($b, $bptr));
if($matchlen)
{
$ops[] = array('=', substr($a, $aptr, $matchlen));
$aptr += $matchlen;
$bptr += $matchlen;
continue;
}
/* Difference found */
$bestlen=0;
$bestpos=array(0,0);
for($atmp = $aptr; $atmp < $alen; $atmp++)
{
for($btmp = $bptr; $btmp < $blen; $btmp++)
{
$matchlen = matchlen(substr($a, $atmp), substr($b, $btmp));
if($matchlen>$bestlen)
{
$bestlen=$matchlen;
$bestpos=array($atmp,$btmp);
}
if($matchlen >= $blen-$btmp)break;
}
}
if(!$bestlen)break;
$adifflen = $bestpos[0] - $aptr;
$bdifflen = $bestpos[1] - $bptr;
if($adifflen)
{
$ops[] = array('-', substr($a, $aptr, $adifflen));
$aptr += $adifflen;
}
if($bdifflen)
{
$ops[] = array('+', substr($b, $bptr, $bdifflen));
$bptr += $bdifflen;
}
$ops[] = array('=', substr($a, $aptr, $bestlen));
$aptr += $bestlen;
$bptr += $bestlen;
}
if($aptr < $alen)
{
/* b has too much stuff */
$ops[] = array('-', substr($a, $aptr));
}
if($bptr < $blen)
{
/* a has too little stuff */
$ops[] = array('+', substr($b, $bptr));
}
return $ops;
}
Example:
$tab = calcdiffer('Tämä on jonkinlainen testi',
'Tämä ei ole minkäänlainen testi.');
$ops = array('='=>'Ok', '-'=>'Remove',
'+'=>'Add');
foreach($tab as $k)
echo $ops[$k[0]], " '", $k[1], "'\n";
Example output:
Ok 'Tämä '
Remove 'on jonki'
Add 'ei ole minkää'
Ok 'nlainen testi'
Add '.'
--
http://www.php.net/manual/en/function.levenshtein.php
http://master.php.net/manage/user-notes.php?action=edit+24289
http://master.php.net/manage/user-notes.php?action=delete+24289
http://master.php.net/manage/user-notes.php?action=reject+24289