php - 变音符号的编辑距离

Question

在 PHP 中，我使用函数 levenshtein() 计算 Levenshtein 距离。对于简单字符，它按预期工作，但对于示例中的变音符号字符

echo levenshtein('à', 'a');

它返回“2”。在这种情况下，只需进行一次替换，因此我希望它返回“1”。

我错过了什么吗？

Answer 1

我认为 this comment from the PHP manual 可能会有用作为这个问题的答案发布，所以这里是:-

levenshtein 函数单独处理输入字符串的每个字节。那么对于多字节编码，例如UTF-8，它可能会给出误导性的结果。

带有法语口音的单词示例:- levenshtein('notre', 'votre') = 1- levenshtein('notre', 'nôtre') = 2(哈？!)

您可以轻松找到 levenshtein 函数的多字节兼容 PHP 实现，但它当然会比 C 实现慢得多。

另一个选项是将字符串转换为单字节(无损)编码，以便它们可以提供给快速核心 levenshtein 函数。

这是我在存储 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 ms- utf8 到 ext-ascii 转换 + 核心功能:90 ms- 完整的 php 实现:3000 毫秒