note 100589 deleted from function.levenshtein by danbrown
| From: | danbrown@php.net | Date: | Mon, 25 Oct 2010 16:03:30 +0000 |
| Subject: | note 100589 deleted from function.levenshtein by danbrown | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-173444@lists.php.net to get a copy of this message | ||
Note Submitter: Serg Lifinsky
----
/*
PHP Levenshtein function with best performance and minimal memory usage.
*/
function distance($source, $dest) {
if ($source == $dest) return 0;
$slen = strlen($source);
$dlen = strlen($dest);
$dist = array(0 => range(0, $dlen));
for ($i = 0; $i < $slen; $i++) {
$next_i = $i + 1;
$dist[$next_i] = array($next_i);
for ($j = 0; $j < $dlen; $j++) {
$cost = $source{$i} == $dest{$j} ? 0 : 1;
$dist[$next_i][$j + 1] = min(
$dist[$i][$j + 1] + 1, // deletion
$dist[$next_i][$j] + 1, // insertion
$dist[$i][$j] + $cost // substitution
);
}
unset($dist[$i]);
}
return $dist[$i][$j];
}