note 85304 deleted from function.levenshtein by mgf
| From: | mgf@php.net | Date: | Thu, 28 Aug 2008 13:21:40 +0000 |
| Subject: | note 85304 deleted from function.levenshtein by mgf | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-143932@lists.php.net to get a copy of this message | ||
Note Submitter: paulrowe at iname dot com
----
Here is an implementation of the Levenshtein Distance calculation that only uses a one-dimensional
array. This implementation was inspired by maze generation algorithms that also use only
one-dimensional arrays. I've included lines that can be un-commented should you want
"debug output".
<?php
/*
* This function starts out with several checks in an attempt to save time.
* 1. If the left string is empty, the length of the right is returned.
* 2. If the right string is empty, the length of the left is returned.
* 3. If the strings are equal, a zero-distance is returned.
* 4. If the left string is contained within the right string, the difference in length is
returned.
* 5. 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($sLeft, $sRight)
{
$nLeftLength = strlen($sLeft);
$nRightLength = strlen($sRight);
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 {
// echo '<table border=0><tr><td></td>';
// for ($nRightPos = 0; $nRightPos < $nRightLength; ++$nRightPos)
// echo '<td align=center><b>' . $sRight[$nRightPos] .
'</b></td>';
// echo '</tr>';
$nsDistance = range(0, $nRightLength + 1);
for ($nLeftPos = 1; $nLeftPos <= $nLeftLength; ++$nLeftPos)
{
$cLeft = $sLeft[$nLeftPos - 1];
// echo '<tr><td align=right><b>' . $cLeft .
'</b></td>';
$nDiagonal = $nsDistance[0];
$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], $nsDistance[$nRightPos - 1],
$nDiagonal) + $nCost;
// echo '<td align=right>' . $nsDistance[$nRightPos] .
'</td>';
$nDiagonal = $nNewDiagonal;
}
// echo '</tr>';
}
// echo '</table>';
return $nsDistance[$nRightLength];
}
}
?>