PHP – 优化 – 具有优先级的Levenshtein距离

我试图用一个小插件来实现 levenshtein algorithm.我想优先考虑具有连续匹配字母的值.我已经尝试使用下面的代码实现我自己的形式：

function levenshtein_raTing($String1,$String2) {
    $GLOBALS['lvn_memo'] = array();
    return lev($String1,strlen($String1),$String2,strlen($String2));
}

function lev($s1,$s1x,$s1l,$s2,$s2x,$s2l,$cons = 0) {
    $key = $s1x . "," . $s1l . "," . $s2x . "," . $s2l;
    if (isset($GLOBALS['lvn_memo'][$key])) return $GLOBALS['lvn_memo'][$key];

    if ($s1l == 0) return $s2l;
    if ($s2l == 0) return $s1l;

    $cost = 0;
    if ($s1[$s1x] != $s2[$s2x]) $cost = 1;
    else $cons -= 0.1;

    $dist = min(
                (lev($s1,$s1x + 1,$s1l - 1,$cons) + 1),(lev($s1,$s2x + 1,$s2l - 1,$cons) + $cost)
            );
    $GLOBALS['lvn_memo'][$key] = $dist + $cons;
    return $dist + $cons;
}@H_607_3@ 
 
你应该注意$cons – = 0.1;是我添加值以确定连续值的优先级的部分.该公式将针对大型字符串数据库进行检查. (高达20,000 – 50,000)我已经使用php内置的levenshtein进行了基准测试
 
  
 
@R_450_8798@ge      Time Change     Memory
php          N/A             9300128
End php      1ms             9300864
End Mine     20ms            9310736
Array
(
    [0] => 3
    [1] => 3
    [2] => 0
)
Array
(
    [0] => 2.5
    [1] => 1.9
    [2] => -1.5
)@H_607_3@ 
 
基准测试代码：
 
  
 
$String1 = "kitten";
$String2 = "sitter";
$String3 = "sitTing";

$log = new Logger("php");
$distances = array();
$distances[] = levenshtein($String1,$String3);
$distances[] = levenshtein($String2,$String3);
$distances[] = levenshtein($String3,$String3);
$log->log("End php");

$distances2 = array();
$distances2[] = levenshtein_raTing($String1,$String3);
$distances2[] = levenshtein_raTing($String2,$String3);
$distances2[] = levenshtein_raTing($String3,$String3);
$log->log("End Mine");
echo $log->status();

echo "<pre>" . print_r($distances,truE) . "</pre>";
echo "<pre>" . print_r($distances2,truE) . "</pre>";@H_607_3@ 
 
我认识到php的内置功能可能总是比我的本质更快.但我想知道是否有办法加快我的速度？
 
 
所以问题是：有没有办法加快速度？我在这里的另一种选择是运行levenshtein,然后搜索最高的X结果并另外优先考虑它们.
 
 
根据Leigh的评论,复制php内置的Levenhstein形式将时间缩短到3ms. (编辑：发布连续字符扣除的版本.这可能需要调整,似乎工作.)
 
  
 
function levenshtein_raTing($s1,$cons = 0,$cost_ins = 1,$cost_rep = 1,$cost_del = 1) {
    $s1l = strlen($s1);
    $s2l = strlen($s2);
    if ($s1l == 0) return $s2l;
    if ($s2l == 0) return $s1l;

    $p1 = array();
    $p2 = array();

    for ($i2 = 0; $i2 <= $s2l; ++$i2) {
        $p1[$i2] = $i2 * $cost_ins;
    }

    $cons = 0;
    $cons_count = 0;
    $cln = 0;
    $tbl = $s1;
    $lst = false;

    for ($i1 = 0; $i1 < $s1l; ++$i1) {
        $p2[0] = $p1[0] + $cost_del;

        $srch = true;

        for($i2 = 0; $i2 < $s2l; ++ $i2) {
            $c0 = $p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep);
            if ($srch && $s2[$i2] == $tbl[$i1]) {
                $tbl[$i1] = "\0";
                $srch = false;
                $cln += ($cln == 0) ? 1 : $cln * 1;
            }

            $c1 = $p1[$i2 + 1] + $cost_del;

            if ($c1 < $c0) $c0 = $c1;
            $c2 = $p2[$i2] + $cost_ins;
            if ($c2 < $c0) $c0 = $c2;

            $p2[$i2 + 1] = $c0;
        }

        if (!$srch && $lst) {
            $cons_count += $cln;
            $cln = 0;
        }
        $lst = $srch;

        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;
    }
    $cons_count += $cln;

    $cons = -1 * ($cons_count * 0.1);
    return $p1[$s2l] + $cons;
}@H_607_3@

define('LEVENSHTEIN_MAX_LENGTH',12);

function lev2($s1,$cost_del = 1)
{
    $l1 = strlen($s1);
    $l2 = strlen($s2);

    if ($l1 == 0) {
        return $l2 * $cost_ins;
    }
    if ($l2 == 0) {
        return $l1 * $cost_del;
    }

    if (($l1 > LEVENSHTEIN_MAX_LENGTH) || ($l2 > LEVENSHTEIN_MAX_LENGTH)) {
        return -1;
    }

    $p1 = array();
    $p2 = array();

    for ($i2 = 0; $i2 <= $l2; $i2++) {
        $p1[$i2] = $i2 * $cost_ins;
    }

    for ($i1 = 0; $i1 < $l1; $i1++) {
        $p2[0] = $p1[0] + $cost_del;

        for ($i2 = 0; $i2 < $l2; $i2++) {
            $c0 = $p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep);
            $c1 = $p1[$i2 + 1] + $cost_del;
            if ($c1 < $c0) {
                $c0 = $c1;
            }
            $c2 = $p2[$i2] + $cost_ins;
            if ($c2 < $c0) {
                $c0 = $c2;
            }
            $p2[$i2 + 1] = $c0;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;
    }
    return $p1[$l2];
}@H_607_3@ 
 
我做了一个快速的基准测试,比较你的,我的和php的内部函数,每个100,000次迭代,时间以秒为单位.
 
  
 
float(12.954766988754)
float(2.4660499095917)
float(0.14857912063599)@H_607_3@ 
 
显然它还没有进行调整,但我相信它们不会减慢它的速度.
 
 
如果你真的需要更多的速度提升,一旦你弄清楚如何改变这个功能,它应该很容易将你的更改移植回C,复制php函数定义,并实现你自己的本机C版本你修改过的功能.
 
 
有很多关于如何进行php扩展的教程,所以如果你决定沿着那条路走下去,你不应该有那么多困难.
 
 
编辑：
 
 
我注意到,正在寻找进一步改善它的方法
 
  
 
$c0 = $p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep);
        $c1 = $p1[$i2 + 1] + $cost_del;
        if ($c1 < $c0) {
            $c0 = $c1;
        }
        $c2 = $p2[$i2] + $cost_ins;
        if ($c2 < $c0) {
            $c0 = $c2;
        }@H_607_3@ 
 
是相同的
 
  
 
$c0 = min(
            $p1[$i2 + 1] + $cost_del,$p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep),$c2 = $p2[$i2] + $cost_ins
        );@H_607_3@ 
 
我认为这与代码中的min块直接相关.但是,这会显着减慢代码速度. (我猜它是额外函数调用的开销)
 
 
使用min()块作为第二个时序的基准.
 
  
 
float(2.484846830368)
float(3.6055288314819)@H_607_3@ 
 
你是对的第二个$cost_ins不属于 – 我的复制/粘贴失败.