PHP levenshtein 字符串函数

  • 定义和用法

    levenshtein - 计算两个字符串之间的编辑距离
  • 版本支持

    PHP4 PHP5 PHP7
    V4.0.1(含)+支持 支持 支持
  • 语法

    levenshtein ( string $str1 , string $str2 )
    levenshtein  ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )
    编辑距离,是指两个字串之间,通过替换、插入、删除等操作将字符串str1转换成str2所需要操作的最少字符数量。 该算法的复杂度是 O(m*n),其中 n 和 m 分别是str1 和str2的长度 (当和算法复杂度为O(max(n,m)**3)的similar_text()相比时,此函数还是相当不错的,尽管仍然很耗时。)。在最简单的形式中,该函数只以两个字符串作为参数,并计算通过插入、替换和删除等操作将str1转换成str2所需要的操作次数。第二种变体将采用三个额外的参数来定义插入、替换和删除操作的次数。此变体比第一种更加通用和适应,但效率不高。
  • 参数

    参数 必需的 描述
    str1 求编辑距离中的其中一个字符串
    str2 求编辑距离中的另一个字符串
    cost_ins 定义插入次数
    cost_rep 定义替换次数
    cost_del 定义删除次数
  • 返回值

    此函数返回两个字符串参数之间的编辑距离,如果其中一个字符串参数长度大于限制的255个字符时,返回-1。
  • 示例

    <?php
    // 输入拼写错误的单词
    $input = 'carrrot';
    
    // 要检查的单词数组
    $words  = array('apple','pineapple','banana','orange', 'radish','carrot','pea','bean','potato');
    
    // 目前没有找到最短距离
    $shortest = -1;
    
    // 遍历单词来找到最接近的
    foreach ($words as $word) {
    
       // 计算输入单词与当前单词的距离
       $lev = levenshtein($input, $word);
    
       // 检查完全的匹配
       if ($lev == 0) {
    
           // 最接近的单词是这个(完全匹配)
           $closest = $word;
           $shortest = 0;
    
           // 退出循环;我们已经找到一个完全的匹配
           break;
       }
    
       // 如果此次距离比上次找到的要短
       // 或者还没找到接近的单词
       if ($lev <= $shortest || $shortest < 0) {
           // 设置最接近的匹配以及它的最短距离
           $closest  = $word;
           $shortest = $lev;
       }
    }
    
    echo "输入的单词是: $input\n";
    echo '<br/>';
    if ($shortest == 0) {
       echo "精确匹配发现: $closest\n";
    } else {
       echo "你的意思是: $closest?\n";
    }
    
    ?>
    
    尝试一下
  • 相关函数

    soundex() - 计算字符串的soundex键
    similar_text() - 计算两个字符串的相似度
    metaphone() - 计算字符串的变音位键