Damerau-Levenshtein php

Question

Estoy buscando una implementaciones del algoritmo Damerau–Levenshtein para PHP, pero parece que no puedo encontrar nada con mi amigo google. Hasta ahora tengo que usar PHP implementado Levenshtein (sin transposición Damerau, que es muy importante), u obtener un código fuente original (en C, C++, C#, Perl) y escribirlo (traducirlo) a PHP.

¿Alguien tiene conocimiento de una implementación de PHP?

Estoy usando soundex y metafonía doble para la extensión "Quiso decir:" en mi intranet corporativa, y quiero implementar el algoritmo Damerau-Levenshtein para ayudarme a ordenar mejor los resultados. Algo similar a esta idea: http://www.briandrought.com/blog/?p=66, mi implementación es similar a los primeros 5 pasos.

Answer 1

Tuve un stab at it una solución recursiva mientras estaba de vuelta.

/* 
* 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

Tenga una mirada en our implementation (con pruebas y documentación).

Answer 3

¿Qué tal si usamos la función incorporada de 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)