note 85387 modified in function.levenshtein by mgf
| From: | mgf@php.net | Date: | Thu, 28 Aug 2008 13:20:51 +0000 |
| Subject: | note 85387 modified in function.levenshtein by mgf | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-143931@lists.php.net to get a copy of this message | ||
[EDITOR'S NOTE: original post and 2 corrections combined into 1 -- mgf]
Here is an implementation of the Levenshtein Distance calculation that only uses a one-dimensional
array and doesn't have a limit to the string length. This implementation was inspired by maze
generation algorithms that also use only one-dimensional arrays.
I have tested this function with two 532-character strings and it completed in 0.6-0.8 seconds.
<?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)
{
$sLeft = (strlen($s1) > strlen($s2)) ? $s1 : $s2;
$sRight = (strlen($s1) > strlen($s2)) ? $s2 : $s1;
$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 {
$nsDistance = range(1, $nRightLength + 1);
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];
}
}
?>
--was--
Here is a revised version of this Levenshtein implementation with the fixed logic and memory-saving
technique mentioned in the previous post. It uses a one-dimensional array (and not as a simulated
two-dimensional array) and doesn't have a limit to the string length. The output causes it to
bog down (e.g. comparing two 500+-character strings takes less than 1 second without it, more than a
minute with it).
<?php
function LevenshteinDistance($s1, $s2)
{
$sLeft = (strlen($s1) > strlen($s2)) ? $s1 : $s2;
$sRight = (strlen($s1) > strlen($s2)) ? $s2 : $s1;
$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 {
$nsDistance = range(1, $nRightLength + 1);
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];
}
}
?>
http://php.net/manual/en/function.levenshtein.php