Damerau-Levenshtein PHP

Question

Ich bin auf der Suche nach einer Implementierungen der Damerau–Levenshtein Algorithmus für PHP, aber es scheint, dass ich nichts mit meinem Freund google finden kann. Bisher muss ich PHP implementiert Levenshtein (ohne Damerau Transposition, die sehr wichtig ist), oder einen originalen Quellcode (in C, C++, C#, Perl) und schreibe (übersetze) es nach PHP.

Kennt jemand eine PHP-Implementierung?

Ich benutze Soundex und Doppel-Metaphone für eine "Dachte ich meine:" Erweiterung auf meinem Firmenintranet, und ich möchte den Damerau-Levenshtein Algorithmus implementieren, um mir zu helfen, die Ergebnisse besser zu sortieren. Ähnlich dieser Idee: http://www.briandrought.com/blog/?p=66, meine Implementierung ähnelt den ersten 5 Schritten.

Answer 1

Ich hatte eine stab at it eine rekursive Lösung während zurück.

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

Schauen Sie sich our implementation an (mit Tests und Dokumentation).

Answer 3

Wie wäre es mit der eingebauten PHP-Funktion ...?

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)