note 101084 added to function.levenshtein
| From: | andrejsatgmail at osu1 dot php dot net | Date: | Thu, 25 Nov 2010 02:38:55 +0000 |
| Subject: | note 101084 added to function.levenshtein | ||
| Groups: | php.notes | ||
| Request: | Send a blank email to php-notes+get-174343@lists.php.net to get a copy of this message | ||
A ported version of the memory efficient implementation by Sten Hjelmqvist at http://www.codeproject.com/KB/recipes/Levenshtein.aspx
- works 1.5x faster than previous versions posted here (44s vs 63s on 2.5KB strings). If you
don't care about UTF, you can substitute mb_substr for array-like access and get even faster
(24s on the same test set).
I also added trimming of common beginning and end so you can save up to 99% more time â in case
of small edits inside large texts.
<?php
function levenshteinDistance2($str1, $str2)
{
$len1 = mb_strlen($str1);
$len2 = mb_strlen($str2);
// strip common prefix
$i = 0;
do {
if(mb_substr($str1, $i, 1) != mb_substr($str2, $i, 1))
break;
$i++;
$len1--;
$len2--;
} while($len1 > 0 && $len2 > 0);
if($i > 0) {
$str1 = mb_substr($str1, $i);
$str2 = mb_substr($str2, $i);
}
// strip common suffix
$i = 0;
do {
if(mb_substr($str1, $len1-1, 1) != mb_substr($str2, $len2-1, 1))
break;
$i++;
$len1--;
$len2--;
} while($len1 > 0 && $len2 > 0);
if($i > 0) {
$str1 = mb_substr($str1, 0, $len1);
$str2 = mb_substr($str2, 0, $len2);
}
if ($len1 == 0)
return $len2;
if ($len2 == 0)
return $len1;
$v0 = range(0, $len1);
$v1 = array();
for ($i = 1; $i <= $len2; $i++) {
$v1[0] = $i;
$str2j = mb_substr($str2, $i - 1, 1);
for ($j = 1; $j <= $len1; $j++) {
$cost = (mb_substr($str1, $j - 1, 1) == $str2j) ? 0 : 1;
$m_min = $v0[$j] + 1;
$b = $v1[$j - 1] + 1;
$c = $v0[$j - 1] + $cost;
if ($b < $m_min)
$m_min = $b;
if ($c < $m_min)
$m_min = $c;
$v1[$j] = $m_min;
}
$vTmp = $v0;
$v0 = $v1;
$v1 = $vTmp;
}
return $v0[$len1];
}
?>
----
Server IP: 212.93.96.97
Probable Submitter: 89.201.122.133
----
Manual Page -- http://www.php.net/manual/en/function.levenshtein.php
Edit -- https://master.php.net/note/edit/101084
Del: integrated -- https://master.php.net/note/delete/101084/integrated
Del: useless -- https://master.php.net/note/delete/101084/useless
Del: bad code -- https://master.php.net/note/delete/101084/bad+code
Del: spam -- https://master.php.net/note/delete/101084/spam
Del: non-english -- https://master.php.net/note/delete/101084/non-english
Del: in docs -- https://master.php.net/note/delete/101084/in+docs
Del: other reasons-- https://master.php.net/note/delete/101084
Reject -- https://master.php.net/note/reject/101084
Search -- https://master.php.net/manage/user-notes.php