note 87175 added to function.levenshtein
| From: | paulroweatinamedotcom at osu1 dot php dot net | Date: | Sun, 23 Nov 2008 04:57:25 +0000 |
| Subject: | note 87175 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-146832@lists.php.net to get a copy of this message | ||
Once again, some testing (with thanks to Tiago) showed me that there was still an error in the code.
It wasn't coming up with the right distance when a deletion was involved. This is because
there was an error in the way that the distance array was instantiated. (Also, my thanks to the
editor for making this easier on everyone involved.)
<?php
/*
* This function starts out with several checks in an attempt to save time.
* 1. The shorter string is always used as the "right-hand" string (as the size of the
array is based on its length).
* 2. If the left string is empty, the length of the right is returned.
* 3. If the right string is empty, the length of the left is returned.
* 4. If the strings are equal, a zero-distance is returned.
* 5. If the left string is contained within the right string, the difference in length is
returned.
* 6. If the right string is contained within the left string, the difference in length is
returned.
* If none of the above conditions were met, the Levenshtein algorithm is used.
*/
function LevenshteinDistance($s1, $s2)
{
$nLeftLength = strlen($s1);
$nRightLength = strlen($s2);
if ($nLeftLength >= $nRightLength)
{
$sLeft = $s1;
$sRight = $s2;
} else {
$sLeft = $s2;
$sRight = $s1;
$nLeftLength += $nRightLength; // arithmetic swap of two values
$nRightLength = $nLeftLength - $nRightLength;
$nLeftLength -= $nRightLength;
}
if ($nLeftLength == 0)
return $nRightLength;
else if ($nRightLength == 0)
return $nLeftLength;
else if ($sLeft === $sRight)
return 0;
else if (($nLeftLength < $nRightLength) && (strpos($sRight, $sLeft) !== FALSE))
return $nRightLength - $nLeftLength;
else if (($nRightLength < $nLeftLength) && (strpos($sLeft, $sRight) !== FALSE))
return $nLeftLength - $nRightLength;
else {
$nsDistance = range(0, $nRightLength);
for ($nLeftPos = 1; $nLeftPos <= $nLeftLength; ++$nLeftPos)
{
$cLeft = $sLeft[$nLeftPos - 1];
$nDiagonal = $nLeftPos - 1;
$nsDistance[0] = $nLeftPos;
for ($nRightPos = 1; $nRightPos <= $nRightLength; ++$nRightPos)
{
$cRight = $sRight[$nRightPos - 1];
$nCost = ($cRight == $cLeft) ? 0 : 1;
$nNewDiagonal = $nsDistance[$nRightPos];
$nsDistance[$nRightPos] =
min($nsDistance[$nRightPos] + 1,
$nsDistance[$nRightPos - 1] + 1,
$nDiagonal + $nCost);
$nDiagonal = $nNewDiagonal;
}
}
return $nsDistance[$nRightLength];
}
}
?>
----
Server IP: 69.147.83.197
Probable Submitter: 76.18.95.118
----
Manual Page -- http://www.php.net/manual/en/function.levenshtein.php
Edit -- https://master.php.net/note/edit/87175
Del: integrated -- https://master.php.net/note/delete/87175/integrated
Del: useless -- https://master.php.net/note/delete/87175/useless
Del: bad code -- https://master.php.net/note/delete/87175/bad+code
Del: spam -- https://master.php.net/note/delete/87175/spam
Del: non-english -- https://master.php.net/note/delete/87175/non-english
Del: in docs -- https://master.php.net/note/delete/87175/in+docs
Del: other reasons-- https://master.php.net/note/delete/87175
Reject -- https://master.php.net/note/reject/87175
Search -- https://master.php.net/manage/user-notes.php