Damerau-Levenshtein php

Question

Poszukuję implementacji algorytmu Damerau–Levenshtein dla PHP, ale wydaje się, że nie mogę znaleźć niczego z moim przyjacielem google. Do tej pory muszę używać PHP implementowanego Levenshtein (bez transpozycji Damerau, co jest bardzo ważne), lub uzyskać oryginalny kod źródłowy (w C, C++, C#, Perl) i napisać (przetłumaczyć) go do PHP.

Czy ktoś ma wiedzę na temat implementacji PHP?

Używam soundex i podwójną metafonę dla rozszerzenia "Czy masz na myśli:" w moim firmowym intranecie i chcę zaimplementować algorytm Damerau-Levenshtein, aby pomóc mi lepiej sortować wyniki. Coś podobnego do tego pomysłu: http://www.briandrought.com/blog/?p=66, moja implementacja jest podobna do pierwszych 5 kroków.

Answer 1

Miałem stab at it rozwiązanie rekursywne z powrotem.

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

Zobacz our implementation (z testami i dokumentacją).

Answer 3

Co powiesz na samo użycie wbudowanej funkcji 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)