关于PHP的相似度计算函数:levenshtein的使用介绍

使用说明
先看手册上 levenshtein() 函数的说明:

levenshtein() 函数返回两个字符串之间的 Levenshtein 距离。

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

例如把 kitten 转换为 sitting:

sitten (k→s)
sittin (e→i)
sitting (→g)levenshtein() 函数给每个操作(替换、插入和删除)相同的权重。不过,您可以通过设置可选的 insert、replace、delete 参数,来定义每个操作的代价。

语法:

levenshtein(string1,string2,insert,replace,delete)

参数 描述

string1 必需。要对比的第一个字符串。
string2 必需。要对比的第二个字符串。
insert 可选。插入一个字符的代价。默认是 1。
replace 可选。替换一个字符的代价。默认是 1。
delete 可选。删除一个字符的代价。默认是 1。
提示和注释

如果其中一个字符串超过 255 个字符,levenshtein() 函数返回 -1。
levenshtein() 函数对大小写不敏感。
levenshtein() 函数比 similar_text() 函数更快。不过,similar_text() 函数提供需要更少修改的更精确的结果。
例子


代码如下:

<?php
    echo levenshtein("Hello World","ello World");
    echo "<br />";
    echo levenshtein("Hello World","ello World",10,20,30);
    ?>

输出: 1 30

源码分析
levenshtein() 属于标准函数,在/ext/standard/目录下有专门针对此函数实现的文件:levenshtein.c。

levenshtein()会根据参数个数选择实现方式,针对参数为2和参数为5的情况,都会调用 reference_levdist() 函数计算距离。其不同在于对后三个参数,参数为2时,使用默认值1。

并且在实现源码中我们发现了一个在文档中没有说明的情况: levenshtein() 函数还可以传递三个参数,其最终会调用 custom_levdist() 函数。它将第三个参数作为自定义函数的实现,其调用示例如下:


代码如下:

echo levenshtein("Hello World","ello World", 'strsub');

执行会报Warning: The general Levenshtein support is not there yet。这是因为现在这个方法还没有实现,仅仅是放了一个坑在那。

reference_levdist() 函数的实现算法是一个经典的DP问题。

给定两个字符串x和y,求最少的修改次数将x变成y。修改的规则只能是如下三种之一:删除、插入、改变。
用a[i][j]表示把x的前i个字符变成y的前j个字符所需的最少操作次数,则状态转移方程为:


代码如下:

当x[i]==y[j]时:a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
当x[i]!=y[j]时:a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;

在用状态转移方程前,我们需要初始化(n+1)(m+1)的矩阵d,并让第一行和列的值从0开始增长。 扫描两字符串(nm级的),对比字符,使用状态转移方程,最终$a[$l1][$l2]为其结果。

简单实现过程如下:


代码如下:

<?PHP
    $s1 = "abcdd";
    $l1 = strlen($s1);
    $s2 = "aabbd";
    $l2 = strlen($s2);

for ($i = 0; $i < $l1; $i++) {
        $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i < $l2; $i++) {
        $a[$i + 1][0] = $i + 1;
    }

for ($i = 0; $i < $l2; $i++) {
        for ($j = 0; $j < $l1; $j++) {
            if ($s2[$i] == $s1[$j]) {
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
            }else{
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
            }
        }
    }

echo $a[$l1][$l2];
    echo "n";
    echo levenshtein($s1, $s2);

在PHP的实现中,实现者在注释中很清楚的标明:此函数仅优化了内存使用,而没有考虑速度,从其实现算法看,时间复杂度为O(m×n)。其优化点在于将上面的状态转移方程中的二维数组变成了两个一组数组。简单实现如下:


代码如下:

<?PHP
    $s1 = "abcjfdkslfdd";
    $l1 = strlen($s1);
    $s2 = "aab84093840932bd";
    $l2 = strlen($s2);

$dis = 0;
    for ($i = 0; $i <= $l2; $i++){
        $p1[$i] = $i;
    }

for ($i = 0; $i < $l1; $i++){
        $p2[0] = $p1[0] + 1;

for ($j = 0; $j < $l2; $j++){
            if ($s1[$i] == $s2[$j]){
                $dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
            }else{
                $dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  // 注意这里最后一个参数为$p2 
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp; 
    }

echo "n";
    echo $p1[$l2];
    echo "n";
    echo levenshtein($s1, $s2);

如上为PHP内核开发者对前面经典DP的优化,其优化点在于不停的复用两个一维数组,一个记录上次的结果,一个记录这一次的结果。如果按照PHP的参数,分别给三个操作赋值不同的值,在上面的算法中将对应的1变成操作对应的值就可以了。 min函数的第一个参数对应的是修改,第二个参数对应的是删除源码天空,第三个参数对应的是添加。

Levenshtein distance说明
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。Levenshtein distance可以用来:
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测) LD用mn的矩阵存储距离值。

(0)

相关推荐

  • php查询相似度最高的字符串的方法

    本文实例讲述了php查询相似度最高的字符串的方法.分享给大家供大家参考.具体如下: 根据传入的字符串和数组,返回数组中相似度最高的字符串 1. PHP代码如下: function closest_word($input, $words) { $shortest = -1; foreach ($words as $word) { $lev = levenshtein($input, $word); if ($lev == 0) { $closest = $word; $shortest = 0;

  • 如何使用php绘制在图片上的正余弦曲线

    以前用actionscript写动态绘制三角函数曲线,其实php输出三角函数曲线也很简单. 复制代码 代码如下: <?php define("MAX_WIDTH_PIXEL", 600); define("MAX_HEIGHT_PIXEL", 240); //发送标头信息 header("Content-type: image/gif"); //建立图像 $img = imageCreate(MAX_WIDTH_PIXEL, MAX_HEI

  • php数字游戏 计算24算法

    算法思路:把每一个数字看做一个独立的数学表达式,表达式之间加上标点符号组合成新表达式,一共组合4次,表达式之间的所有组合可以通过递归来实现. 代码如下: 复制代码 代码如下: <?php /** * A 24 maker * @version 1.0.0 * @author laruence<laruence at yahoo.com.cn> * @copyright (c) 2009 http://www.laruence.com */ class TwentyFourCal { pu

  • PHP大转盘中奖概率算法实例

    本文实例讲述了PHP大转盘中奖概率算法的实现方法,分享给大家供大家参考.具体如下: 大转盘是最近很多线上网动中一个比较有意思的东西了,下面我们就来看看这个大转盘中奖概率算法与例子,希望对各位有所帮助. 这是一个APP客户端有大转盘抽奖算法,具体如何抽奖当然在我们服务端实现了.下面和大家简单分享一下实现代码: 复制代码 代码如下: header("Content-type: text/html; charset=utf-8"); $prize_arr = array( '0' =>

  • 使用PHP similar text计算两个字符串相似度

    在网站开发中,我们经常使用php similar text 计算两个字符串相似度; 1,similar_text的用法 如果我想计算"ly89cn"和"ly89"的相似程度,有两种表示方法 复制代码 代码如下: echo similar_text('ly89cn', 'ly89'); 这样输出4,因为他们有4个字符相等 复制代码 代码如下: similar_text('ly89cn', 'ly89', $percent); echo $percent; 这样输出80

  • php计算两个整数的最大公约数常用算法小结

    本文实例讲述了php计算两个整数的最大公约数常用算法.分享给大家供大家参考.具体如下: 复制代码 代码如下: <?php //计时,返回秒 function  microtime_float () {     list( $usec ,  $sec ) =  explode ( " " ,  microtime ());     return ((float) $usec  + (float) $sec ); } /////////////////////////////////

  • php 大数据量及海量数据处理算法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题.下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论. 1.Bloom filter 适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集 基本原理及要点: 对于原理来说很简单,位数组+k个独立hash函数.将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明

  • PHP改进计算字符串相似度的函数similar_text()、levenshtein()

    similar_text()中文汉字版 复制代码 代码如下: <?php       //拆分字符串       function split_str($str) {         preg_match_all("/./u", $str, $arr);         return $arr[0];       }              //相似度检测       function similar_text_cn($str1, $str2) {         $arr_1

  • php编写的抽奖程序中奖概率算法

    们先完成后台PHP的流程,PHP的主要工作是负责配置奖项及对应的中奖概率,当前端页面点击翻动某个方块时会想后台PHP发送ajax请求,那么后台PHP根据配置的概率,通过概率算法给出中奖结果,同时将未中奖的奖项信息一并以JSON数据格式发送给前端页面. 先来看概率计算函数 function get_rand($proArr) { $result = ''; //概率数组的总概率精度 $proSum = array_sum($proArr); //概率数组循环 foreach ($proArr as

  • PHP实现的简易版图片相似度比较

    由于相似图片搜索的php实现的 API 不怎么符合我的用途,所以我重新定义 API 的架构,改写成比较简单的函数方式,虽然还是用对象的方式包装. 复制代码 代码如下: <?php    /**   * 图片相似度比较   *   * @version     $Id: ImageHash.php 4429 2012-04-17 13:20:31Z jax $   * @author      jax.hu   *   * <code>   *  //Sample_1   *  $aHas

  • PHP数据分析引擎计算余弦相似度算法示例

    本文实例讲述了PHP数据分析引擎计算余弦相似度算法.分享给大家供大家参考,具体如下: 关于余弦相似度的相关介绍可参考百度百科:余弦相似度 <?php /** * 数据分析引擎 * 分析向量的元素 必须和基准向量的元素一致,取最大个数,分析向量不足元素以0填补. * 求出分析向量与基准向量的余弦值 * @author yu.guo@okhqb.com */ /** * 获得向量的模 * @param unknown_type $array 传入分析数据的基准点的N维向量.|eg:array(1,1

  • PHP中计算字符串相似度的函数代码

    similar_text - 计算两个字符串的相似度 int similar_text ( string $first , string $second [, float &$percent ] ) $first 必需.规定要比较的第一个字符串. $second 必需.规定要比较的第二个字符串. $percent 可选.规定供存储百分比相似度的变量名. 两个字符串的相似程度计算依据 Oliver [1993] 的描述进行.注意该实现没有使用 Oliver 虚拟码中的堆栈,但是却进行了递归调用,这

随机推荐