Расстояние Левенштейна по диакритическим знакам
В PHP я вычисляю расстояние Левенштейна с помощью функции levenshtein (). Для простых символов это работает, как и ожидалось, но для диакритических символов, как в примере
echo levenshtein('à', 'a');
возвращает «2». В этом случае должна быть сделана только одна замена, поэтому я ожидаю, что она вернет «1».
Я что-то пропустил?
Решение
PHP по умолчанию levenshtein(), как и многие функции PHP, не поддерживает многобайтовый режим. Таким образом, при обработке строк с символами Unicode он обрабатывает каждый байт отдельно и изменяет два байта.
Нет многобайтовой версии (т.е. mb_levenshtein()) так что у вас есть два варианта:
1) Повторно внедрите функцию самостоятельно, используя mb_ функции. Возможный пример кода из Gist:
<?php
function levenshtein_php($str1, $str2){
$length1 = mb_strlen( $str1, 'UTF-8');
$length2 = mb_strlen( $str2, 'UTF-8');
if( $length1 < $length2) return levenshtein_php($str2, $str1);
if( $length1 == 0 ) return $length2;
if( $str1 === $str2) return 0;
$prevRow = range( 0, $length2);
$currentRow = array();
for ( $i = 0; $i < $length1; $i++ ) {
$currentRow=array();
$currentRow[0] = $i + 1;
$c1 = mb_substr( $str1, $i, 1, 'UTF-8') ;
for ( $j = 0; $j < $length2; $j++ ) {
$c2 = mb_substr( $str2, $j, 1, 'UTF-8' );
$insertions = $prevRow[$j+1] + 1;
$deletions = $currentRow[$j] + 1;
$substitutions = $prevRow[$j] + (($c1 != $c2)?1:0);
$currentRow[] = min($insertions, $deletions, $substitutions);
}
$prevRow = $currentRow;
}
return $prevRow[$length2];
}
2) Преобразуйте символы Unicode вашей строки в ASCII. Если вы специально хотите рассчитать разницу Левенштейна от диакритических знаков до недиакритических, то, вероятно, это не то, что вам нужно.
Другие решения
Я думал, что это может быть полезно иметь этот комментарий из руководства по PHP опубликовано как ответ на этот вопрос, так что вот оно: —
Функция Левенштейна обрабатывает каждый байт входной строки индивидуально. Тогда для многобайтовых кодировок, таких как UTF-8, это может дать ошибочные результаты.
Пример с французским акцентированным словом:
— Левенштейн (‘notre’, ‘votre’) = 1
— Левенштейн (‘notre’, ‘nôtre’) = 2 (да?!)
Вы можете легко найти многобайтовую совместимую PHP-реализацию функции levenshtein, но она, конечно, будет намного медленнее, чем реализация на C.
Другой вариант — преобразовать строки в однобайтовую кодировку (без потерь), чтобы они могли выполнять функцию быстрого ядра Левенштейна.
Вот функция преобразования, которую я использовал с поисковой системой, хранящей строки UTF-8, и быстрый тест. Надеюсь, это поможет.
<?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($str, &$map)
{
// find all multibyte characters (cf. utf-8 encoding specs)
$matches = array();
if (!preg_match_all('/[\xC0-\xF7][\x80-\xBF]+/', $str, $matches))
return $str; // plain ascii string
// update the encoding map with the characters not already met
foreach ($matches[0] as $mbc)
if (!isset($map[$mbc]))
$map[$mbc] = chr(128 + count($map));
// finally remap non-ascii characters
return strtr($str, $map);
}
// 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 many strings from a database, 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);
}
?>
Результаты (около 6000 звонков)
— базовая функция времени C (однобайтовая): 30 мс
— преобразование utf8 в ext-ascii + основная функция: 90 мс
— полная реализация php: 3000 мс