note 106355 deleted from function.levenshtein by danbrown
| From: | danbrown@php.net | Date: | Mon, 31 Oct 2011 15:14:16 +0000 |
| Subject: | note 106355 deleted from function.levenshtein by danbrown | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-184259@lists.php.net to get a copy of this message | ||
Note Submitter: Anton Fedorov
----
Even more optimized levenshtein implementation, it twice a faster than previous one, but requires a
bit more memory -- instead of mb_* functions, split onto characters into array made first.
function levenshteinDistance3($str1, $str2)
{
$str1 = preg_split("//", $str1);
$str2 = preg_split("//", $str2);
$len1 = count($str1);
$len2 = count($str2);
// strip common prefix
$i = 0;
do {
if($str1[$i] != $str2[$i])
break;
$i++;
$len1--;
$len2--;
} while($len1 > 0 && $len2 > 0);
if($i > 0) {
array_splice($str1, 0, $i);
array_splice($str2, 0, $i);
}
// strip common suffix
$i = 0;
while($len1 > 0 && $len2 > 0) {
if($str1[$len1-1] != $str2[$len2-1])
break;
$i++;
$len1--;
$len2--;
}
if($i > 0) {
array_splice($str1, $len1);
array_splice($str2, $len2);
}
if ($len1 <= 0)
return $len2;
if ($len2 <= 0)
return $len1;
$v0 = range(0, $len1);
$v1 = array_fill(0, $len1, 0);
foreach($str2 as $i => $str2j) {
$v1[0] = $i+1;
foreach($str1 as $j=>$str1c) {
$cost = ($str1c == $str2j) ? 0 : 1;
$a = $v0[$j+1] + 1;
$b = $v1[$j] + 1;
$c = $v0[$j] + $cost;
$v1[$j+1] = $a < $b ? ( $a < $c ? $a : $c ) : ( $b < $c ? $b : $c );
}
$vTmp =& $v0;
$v0 =& $v1;
$v1 =& $vTmp;
}
return $v0[$len1];
}