levenshtein-distance - Damerau-Levenshtein php

Question

我正在寻找 PHP 的Damerau–Levenshtein算法的实现，但我的朋友 google 似乎找不到任何东西。到目前为止，我必须使用 PHP 实现的 Levenshtein（没有 Damerau 转置，这非常重要），或者获取原始源代码（C、C++、C#、Perl）并将其写入（翻译）为 PHP。

有人对 PHP 实现有任何了解吗？

我在公司内部网上使用 soundex 和双变音作为“你的意思是：”扩展，我想实现 Damerau-Levenshtein 算法来帮助我更好地对结果进行排序。类似于这个想法的东西：http ://www.briandrought.com/blog/?p=66 ，我的实现类似于前 5 个步骤。

Answer 1

我在回来的时候尝试了一个递归解决方案。

/*
 * Naïve implementation of Damerau-Levenshtein distance
 * (Does not work when there are neighbouring transpositions)!
 */
function DamerauLevenshtein($S1, $S2)
{
    $L1 = strlen($S1);
    $L2 = strlen($S2);
    if ($L1==0 || $L2==0) {
        // Trivial case: one string is 0-length
        return max($L1, $L2);
    }
    else {
        // The cost of substituting the last character
        $substitutionCost = ($S1[$L1-1] != $S2[$L2-1])? 1 : 0;
        // {H1,H2} are {L1,L2} with the last character chopped off
        $H1 = substr($S1, 0, $L1-1);
        $H2 = substr($S2, 0, $L2-1);
        if ($L1>1 && $L2>1 && $S1[$L1-1]==$S2[$L2-2] && $S1[$L1-2]==$S2[$L2-1]) {
            return min (
                DamerauLevenshtein($H1, $S2) + 1,
                DamerauLevenshtein($S1, $H2) + 1,
                DamerauLevenshtein($H1, $H2) + $substitutionCost,
                DamerauLevenshtein(substr($S1, 0, $L1-2), substr($S2, 0, $L2-2)) + 1
            );
        }
        return min (
            DamerauLevenshtein($H1, $S2) + 1,
            DamerauLevenshtein($S1, $H2) + 1,
            DamerauLevenshtein($H1, $H2) + $substitutionCost
        );
    }
}

Answer 2

看看我们的实现（带有测试和文档）。

Answer 3

只使用内置的 php 函数怎么样...？

http://php.net/manual/en/function.levenshtein.php

int levenshtein ( string $str1 , string $str2 )


int levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del )