note 85387 added to function.levenshtein
| From: | paulroweatinamedotcom at osu1 dot php dot net | Date: | Thu, 28 Aug 2008 00:58:19 +0000 |
| Subject: | note 85387 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-143906@lists.php.net to get a copy of this message | ||
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];
}
}
?>
----
Server IP: 69.147.83.197
Probable Submitter: 75.141.11.200
----
Manual Page -- http://www.php.net/manual/en/function.levenshtein.php
Edit -- https://master.php.net/note/edit/85387
Del: integrated -- https://master.php.net/note/delete/85387/integrated
Del: useless -- https://master.php.net/note/delete/85387/useless
Del: bad code -- https://master.php.net/note/delete/85387/bad+code
Del: spam -- https://master.php.net/note/delete/85387/spam
Del: non-english -- https://master.php.net/note/delete/85387/non-english
Del: in docs -- https://master.php.net/note/delete/85387/in+docs
Del: other reasons-- https://master.php.net/note/delete/85387
Reject -- https://master.php.net/note/reject/85387
Search -- https://master.php.net/manage/user-notes.php