note 113680 added to function.levenshtein

The levenshtein function processes each byte of the input string individually. Then for multibyte encodings, such as UTF-8, it may give misleading results. Example with a french accented word : - levenshtein('notre', 'votre') = 1 - levenshtein('notre', 'nôtre') = 2 (huh ?!) You can easily find a multibyte compliant PHP implementation of the levenshtein function but it will be of course far slower than the C implementation. Another option is to convert the strings to a single-byte (lossless) encoding so that they can feed the fast core levenshtein function. Here is the conversion function I used with a search engine storing UTF-8 strings, and a quick benchmark. I hope it will help. <?php // Convert an UTF-8 encoded string to a single-byte string suitable for // functions such as levenshtein. // // The function simply uses (and updates) a tailored dynamic encoding // (in/out map parameter) where non-ascii characters are remapped to // the range [128-255] in order of appearance. // // Thus it supports up to 128 different multibyte code points max over // the whole set of strings sharing this encoding. // function utf8_to_extended_ascii($s, &$map) { $len = mb_strlen($s, 'utf-8'); if ($len == strlen($s)) // no multibyte characters in this input return $s; // now convert to a single-byte character string, for each multibyte // character we keep only its leading byte as a placeholder $aux = preg_replace('/[\x80-\xBF]/', '', $s); // cf. utf-8 encoding specs $maxAscii = chr(127); for ($n = 0; $n != $len; ++$n) { if ($aux[$n] <= $maxAscii) // ascii char continue; // full multibyte sequence of the non-ascii character $mbs = mb_substr($s, $n, 1, 'utf-8'); if (!isset($map[$mbs])) // character not met yet, update the encoding map { $subst = chr(128 + count($map)); $map[$mbs] = $subst; $aux[$n] = $subst; } else $aux[$n] = $map[$mbs]; } return $aux; } // Didactic example showing the usage of the previous conversion function but, // for better performance, in a real application with a single input string matched // against a large number of database strings, you will probably want to pre-encode // the input only once. // function levenshtein_utf8($s1, $s2) { $charMap = array(); $s1 = utf8_to_extended_ascii($s1, $charMap); $s2 = utf8_to_extended_ascii($s2, $charMap); return levenshtein($s1, $s2); } ?> Results (for about 6000 calls) - reference time core C function (single-byte) : 30 ms - utf8 to ext-ascii conversion + core function : 100 ms - full php implementation : 3000 ms ---- Server IP: 64.71.164.2 Probable Submitter: 81.57.70.126 ---- Manual Page -- http://php.net/manual/en/function.levenshtein.php Edit -- https://master.php.net/note/edit/113680 Del: integrated -- https://master.php.net/note/delete/113680/integrated Del: useless -- https://master.php.net/note/delete/113680/useless Del: bad code -- https://master.php.net/note/delete/113680/bad+code Del: spam -- https://master.php.net/note/delete/113680/spam Del: non-english -- https://master.php.net/note/delete/113680/non-english Del: in docs -- https://master.php.net/note/delete/113680/in+docs Del: other reasons-- https://master.php.net/note/delete/113680 Reject -- https://master.php.net/note/reject/113680 Search -- https://master.php.net/manage/user-notes.php