5

私は少しのアドオンでレーベンシュタインアルゴリズムを実装しようとしています。文字が連続して一致する値を優先したい。以下のコードを使用して、独自の形式を実装してみました。

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

$cons -= 0.1;連続する値を優先するために値を追加している部分であることに注意してください。この式は、文字列の大規模なデータベースに対してチェックします。（20,000〜50,000もの高さ）PHPが組み込まれているベンチマークテストを実行しました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
)

ベンチマークテストコード：

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

PHPの組み込み関数は、おそらく私の性質よりも常に高速であると認識しています。しかし、私は私のスピードを上げる方法があるかどうか疑問に思っていますか？

だから質問：これをスピードアップする方法はありますか？ここでの私の代替案は、レーベンシュタインを実行してから、その中で最も高いXの結果を検索し、それらにさらに優先順位を付けることです。

Leighのコメントに基づくと、PHPの組み込み形式のLevenhsteinをコピーすると、時間が3ミリ秒に短縮されました。（編集：連続した文字の控除を含むバージョンを投稿しました。これは、機能しているように見えるため、微調整が必​​要な場合があります。）

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

1 に答える 1

3

関数の主な速度低下は、再帰的であるという事実だと思います。

コメントで述べたように、PHP関数呼び出しはエンジンにとって非常に重い作業であることが知られています。

PHP自体levenshteinはループとして実装され、挿入、置換、および削除にかかるコストの現在の合計を維持します。

コードをループに変換した場合も、パフォーマンスが大幅に向上することは間違いありません。

あなたのコードが何をしているのか正確にはわかりませんが、出発点としてネイティブCコードをPHPに移植しました。

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

私はあなた、私のもの、そしてPHPの内部関数を比較する簡単なベンチマークを行いました。それぞれ100,000回の反復で、時間は秒単位です。

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

明らかに、まだ微調整は行われていませんが、それほど遅くなることはないと確信しています。

本当にスピードを上げる必要がある場合は、この関数を変更する方法を理解したら、変更を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;
        }

と同じです

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

minこれは、コード内のブロックに直接関係していると思います。ただし、これによりコードの速度が大幅に低下します。（私はそれが余分な関数呼び出しのオーバーヘッドだと思います）

min()2番目のタイミングとしてブロックを使用したベンチマーク。

float(2.484846830368)
float(3.6055288314819)

あなたは2番目が属していないことについて正しかった$cost_ins-私の側でコピー/貼り付けは失敗する。

于 2013-01-25T17:04:48.267 に答える