note 85378 deleted from function.levenshtein by mgf
| From: | mgf@php.net | Date: | Thu, 28 Aug 2008 13:22:12 +0000 |
| Subject: | note 85378 deleted from function.levenshtein by mgf | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-143933@lists.php.net to get a copy of this message | ||
Note Submitter: paulrowe at iname dot com
----
I just noticed that there is a flaw in the logic.
That is, the code that says:
<?php
$nsDistance[$nRightPos] = min($nsDistance[$nRightPos], $nsDistance[$nRightPos - 1], $nDiagonal) +
$nCost;
?>
should say:
<?php
$nsDistance[$nRightPos] = min($nsDistance[$nRightPos] + 1, $nsDistance[$nRightPos - 1] + 1,
$nDiagonal + $nCost);
?>
Also, you can reduce memory usage by first checking for the shorter string and using that as the
"right-hand" string (on which the size of the array is based). I have tested this
function with two 532-character strings and it completed in 0.6-0.8 seconds.