note 106355 added to function.levenshtein

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]; } ---- Server IP: 195.54.192.44 Probable Submitter: 178.49.200.67 ---- Manual Page -- http://www.php.net/manual/en/function.levenshtein.php Edit -- https://master.php.net/note/edit/106355 Del: integrated -- https://master.php.net/note/delete/106355/integrated Del: useless -- https://master.php.net/note/delete/106355/useless Del: bad code -- https://master.php.net/note/delete/106355/bad+code Del: spam -- https://master.php.net/note/delete/106355/spam Del: non-english -- https://master.php.net/note/delete/106355/non-english Del: in docs -- https://master.php.net/note/delete/106355/in+docs Del: other reasons-- https://master.php.net/note/delete/106355 Reject -- https://master.php.net/note/reject/106355 Search -- https://master.php.net/manage/user-notes.php