note 85304 added to function.levenshtein

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]; } } ?> ---- 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/85304 Del: integrated -- https://master.php.net/note/delete/85304/integrated Del: useless -- https://master.php.net/note/delete/85304/useless Del: bad code -- https://master.php.net/note/delete/85304/bad+code Del: spam -- https://master.php.net/note/delete/85304/spam Del: non-english -- https://master.php.net/note/delete/85304/non-english Del: in docs -- https://master.php.net/note/delete/85304/in+docs Del: other reasons-- https://master.php.net/note/delete/85304 Reject -- https://master.php.net/note/reject/85304 Search -- https://master.php.net/manage/user-notes.php