Similitud de cadenas en PHP: Función tipo levenshtein para cadenas largas

Question

La función levenshtein en PHP funciona en cadenas con una longitud máxima de 255. Cuáles son buenas alternativas para calcular una puntuación de similitud de oraciones en PHP.

Básicamente tengo una base de datos de oraciones, y quiero encontrar duplicados aproximados. similar_text función no me está dando resultados esperados. ¿Cuál es la manera más fácil para mí para detectar frases similares, como a continuación:

$ss="Jack is a very nice boy, isn't he?"; 
$pp="jack is a very nice boy is he"; 

$ss=strtolower($ss); // convert to lower case as we dont care about case 
$pp=strtolower($pp); 

$score=similar_text($ss, $pp); 
echo "$score %\n"; // Outputs just 29 % 

$score=levenshtein ($ss, $pp); 
echo "$score\n"; // Outputs '5', which indicates they are very similar. But, it does not work for more than 255 chars :(

Answer 1

El algoritmo tiene una complejidad levenshtein momento de O(n*m), donde n y m son las longitudes de las dos cadenas de entrada. Esto es bastante costoso y calcular esa distancia para cadenas largas llevará mucho tiempo.

Para frases enteras, es posible que desee utilizar un algoritmo de diff lugar, véase por ejemplo: Highlight the difference between two strings in PHP

Una vez dicho esto, PHP también proporciona la función similar_text que tiene una complejidad aún peor (O(max(n,m)**3)), pero parece funcionar en cadenas más largas.

Answer 2

Puede intentar con similar_text.
Puede ser bastante lento con más de 20,000 caracteres (3-5 segundos) pero en el ejemplo que mencionas solo con oraciones, esto funcionará perfectamente para ese uso.

Una cosa a tener en cuenta es que al comparar cadenas de diferentes tamaños no obtendrá el 100%. Por ejemplo, si comparas "él" con "cabeza", obtendrías una coincidencia del 50%.

Answer 3

He encontrado que el Smith Waterman Gotoh es el mejor algoritmo para comparar oraciones. Más información in this answer. Aquí está el ejemplo del código PHP:

class SmithWatermanGotoh 
{ 
    private $gapValue; 
    private $substitution; 

    /** 
    * Constructs a new Smith Waterman metric. 
    * 
    * @param gapValue 
    *   a non-positive gap penalty 
    * @param substitution 
    *   a substitution function 
    */ 
    public function __construct($gapValue=-0.5, 
       $substitution=null) 
    { 
     if($gapValue > 0.0) throw new Exception("gapValue must be <= 0"); 
     //if(empty($substitution)) throw new Exception("substitution is required"); 
     if (empty($substitution)) $this->substitution = new SmithWatermanMatchMismatch(1.0, -2.0); 
     else $this->substitution = $substitution; 
     $this->gapValue = $gapValue; 
    } 

    public function compare($a, $b) 
    { 
     if (empty($a) && empty($b)) { 
      return 1.0; 
     } 

     if (empty($a) || empty($b)) { 
      return 0.0; 
     } 

     $maxDistance = min(mb_strlen($a), mb_strlen($b)) 
       * max($this->substitution->max(), $this->gapValue); 
     return $this->smithWatermanGotoh($a, $b)/$maxDistance; 
    } 

    private function smithWatermanGotoh($s, $t) 
    { 
     $v0 = []; 
     $v1 = []; 
     $t_len = mb_strlen($t); 
     $max = $v0[0] = max(0, $this->gapValue, $this->substitution->compare($s, 0, $t, 0)); 

     for ($j = 1; $j < $t_len; $j++) { 
      $v0[$j] = max(0, $v0[$j - 1] + $this->gapValue, 
        $this->substitution->compare($s, 0, $t, $j)); 

      $max = max($max, $v0[$j]); 
     } 

     // Find max 
     for ($i = 1; $i < mb_strlen($s); $i++) { 
      $v1[0] = max(0, $v0[0] + $this->gapValue, $this->substitution->compare($s, $i, $t, 0)); 

      $max = max($max, $v1[0]); 

      for ($j = 1; $j < $t_len; $j++) { 
       $v1[$j] = max(0, $v0[$j] + $this->gapValue, $v1[$j - 1] + $this->gapValue, 
         $v0[$j - 1] + $this->substitution->compare($s, $i, $t, $j)); 

       $max = max($max, $v1[$j]); 
      } 

      for ($j = 0; $j < $t_len; $j++) { 
       $v0[$j] = $v1[$j]; 
      } 
     } 

     return $max; 
    } 
} 

class SmithWatermanMatchMismatch 
{ 
    private $matchValue; 
    private $mismatchValue; 

    /** 
    * Constructs a new match-mismatch substitution function. When two 
    * characters are equal a score of <code>matchValue</code> is assigned. In 
    * case of a mismatch a score of <code>mismatchValue</code>. The 
    * <code>matchValue</code> must be strictly greater then 
    * <code>mismatchValue</code> 
    * 
    * @param matchValue 
    *   value when characters are equal 
    * @param mismatchValue 
    *   value when characters are not equal 
    */ 
    public function __construct($matchValue, $mismatchValue) { 
     if($matchValue <= $mismatchValue) throw new Exception("matchValue must be > matchValue"); 

     $this->matchValue = $matchValue; 
     $this->mismatchValue = $mismatchValue; 
    } 

    public function compare($a, $aIndex, $b, $bIndex) { 
     return ($a[$aIndex] === $b[$bIndex] ? $this->matchValue 
       : $this->mismatchValue); 
    } 

    public function max() { 
     return $this->matchValue; 
    } 

    public function min() { 
     return $this->mismatchValue; 
    } 
} 

$str1 = "Jack is a very nice boy, isn't he?"; 
$str2 = "jack is a very nice boy is he"; 
$o = new SmithWatermanGotoh(); 
echo $o->compare($str1, $str2);