代码之家  ›  专栏  ›  技术社区  ›  Radu Maris

Damerau Levenshtein菲律宾

  •  9
  • Radu Maris  · 技术社区  · 14 年前

    我正在寻找 Damerau–Levenshtein

    有人知道PHP实现吗?

    http://www.briandrought.com/blog/?p=66

    3 回复  |  直到 14 年前
        1
  •  6
  •   Adam    14 年前

    我有一个 stab at it 返回时的递归解决方案。

    /*
     * 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
            );
        }
    }
    
        2
  •  3
  •   tersmitten    10 年前

    看一看 our implementation (包括测试和文件)。

        3
  •  -1
  •   John Peterson    8 年前

    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 )