dongyan1491 2013-01-25 16:13
浏览 97
已采纳

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

I am trying to implement the levenshtein algorithm with a little addon. I want to prioritize values that have consecutive matching letters. I've tried implementing my own form of it using the code below:

function levenshtein_rating($string1, $string2) {
    $GLOBALS['lvn_memo'] = array();
    return lev($string1, 0, strlen($string1), $string2, 0, 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, $s2, $s2x, $s2l, $cons) + 1), 
                (lev($s1, $s1x, $s1l, $s2, $s2x + 1, $s2l - 1, $cons) + 1), 
                (lev($s1, $s1x + 1, $s1l - 1, $s2, $s2x + 1, $s2l - 1, $cons) + $cost)
            );
    $GLOBALS['lvn_memo'][$key] = $dist + $cons;
    return $dist + $cons;
}

You should note the $cons -= 0.1; is the part where I am adding a value to prioritize consecutive values. This formula will be checking against a large database of strings. (As high as 20,000 - 50,000) I've done a benchmark test with PHP's built in levenshtein

Message      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
)

Benchmark Test Code:

$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>";

I recognize that PHP's built in function will probably always be faster than mine by nature. But I am wondering if there is a way to speed mine up?

So the question: Is there a way to speed this up? My alternative here is to run levenshtein and then search through the highest X results of that and prioritize them additionally.


Based on Leigh's comment, copying PHP's built in form of Levenhstein lowered the time down to 3ms. (EDIT: Posted the version with consecutive character deductions. This may need tweaked, by appears to work.)

function levenshtein_rating($s1, $s2, $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;
}
  • 写回答

1条回答 默认 最新

  • duan051347 2013-01-25 17:04
    关注

    I think the major slowdown in your function is the fact that it's recursive.

    As I've said in my comments, PHP function calls are notoriously heavy work for the engine.

    PHP itself implements levenshtein as a loop, keeping a running total of the cost incurred for inserts, replacements and deletes.

    I'm sure if you converted your code to a loop as well you'd see some massive performance increases.

    I don't know exactly what your code is doing, but I have ported the native C code to PHP to give you a starting point.

    define('LEVENSHTEIN_MAX_LENGTH', 12);
    
    function lev2($s1, $s2, $cost_ins = 1, $cost_rep = 1, $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];
    }
    

    I did a quick benchmark comparing yours, mine, and PHPs internal functions, 100,000 iterations each, time is in seconds.

    float(12.954766988754)
    float(2.4660499095917)
    float(0.14857912063599)
    

    Obviously it hasn't got your tweaks in it yet, but I'm sure they wont slow it down that much.

    If you really need more of a speed boost, once you have worked out how to change this function, it should be easy enough to port your changes back into C, make a copy of PHPs function definitions, and implement your own native C version of your modified function.

    There's lots of tutorials out there on how to make PHP extensions, so you shouldn't have that much difficulty if you decide to go down that route.

    Edit:

    Was looking at ways to improve it further, I noticed

            $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;
            }
    

    Is the same as

            $c0 = min(
                $p1[$i2 + 1] + $cost_del,
                $p1[$i2] + (($s1[$i1] == $s2[$i2]) ? 0 : $cost_rep),
                $c2 = $p2[$i2] + $cost_ins
            );
    

    Which I think directly relates to the min block in your code. However, this slows down the code quite significantly. (I guess its the overhead of the extra function call)

    Benchmarks with the min() block as the second timing.

    float(2.484846830368)
    float(3.6055288314819)
    

    You were right about the second $cost_ins not belonging - copy/paste fail on my part.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题