¿Cómo puedo encontrar la subcadena común más grande entre dos cadenas en PHP?

Question

¿Hay un algoritmo rápido para encontrar la subcadena común más grande en dos strings o es un problema de NPComplete?

En PHP que puedo encontrar una aguja en un pajar:

<?php 

if (strstr("there is a needle in a haystack", "needle")) { 
    echo "found<br>\n"; 
} 
?> 

supongo que podría hacer esto en un bucle sobre uno de los strings pero eso sería muy caro! Especialmente porque mi aplicación de esto es buscar en una base de datos de correo electrónico y buscar correo no deseado (es decir, correos electrónicos similares enviados por la misma persona).

¿Alguien tiene algún código PHP que puedan tirar por ahí?

Answer 1

He encontrado a relevant wikipedia article. No es un problema completo de NP, se puede hacer en el tiempo O (mn) usando un algoritmo de programación dinámica.

En PHP encontré la función similar_text muy útil. Aquí hay un ejemplo de código para recuperar una serie de correos electrónicos de texto y recorrerlos y encontrar los que son 90% similares entre sí. Nota: Algo como esto no es escalable:

<?php 
// Gather all messages by a user into two identical associative arrays 
$getMsgsRes = mysql_query(SELECT * FROM email_messages WHERE from = '$someUserID'); 
while($msgInfo = mysql_fetch_assoc($getMsgsRes)) 
{ 
    $msgsInfo1[] = $msgInfo; 
    $msgsInfo2[] = $msgInfo; 
} 

// Loop over msgs and compare each one to every other 
foreach ($msgsInfo1 as $msg1) 
    foreach ($msgsInfo2 as $msg2) 
     similar_text($msg1['msgTxt'],$msg2['msgTxt'],$similarity_pst); 
     if ($similarity_pst > 90) 
      echo "{$msg1['msgID']} is ${similarity_pst}% to {$msg2['msgID']}\n"; 
?> 

Answer 2

Especialmente desde mi aplicación de esto es para buscar una base de datos de correo electrónico y buscar correo no deseado (es decir, correos electrónicos similares enviados por la misma persona).

Creo que deberías estar mirando algoritmos de inferencia de spam bayesiano, no necesariamente la subcadena común más larga.

http://www.devshed.com/c/a/PHP/Implement-Bayesian-inference-using-PHP-Part-1/

Answer 3

La función similar_text puede ser lo que quiera.

Esto calcula la similitud entre dos cadenas. Devuelve el número de caracteres coincidentes en ambas cadenas

También es posible que desee ver en levenshtein

Answer 4

favor, eche un vistazo a Algorithm implementation/Strings/Longest common substring en Wikilibros. No he probado la implementación de PHP, pero parece coincidir con el algoritmo general en la página de Wikipedia.

Answer 5

tarde a este partido, pero aquí es una manera de encontrar la subcadena más común en una matriz de cadenas:

Ejemplo:

$array = array(
    'PTT757LP4', 
    'PTT757A', 
    'PCT757B', 
    'PCT757LP4EV' 
); 
echo longest_common_substring($array); // => T757 

La función:

function longest_common_substring($words) { 
    $words = array_map('strtolower', array_map('trim', $words)); 
    $sort_by_strlen = create_function('$a, $b', 'if (strlen($a) == strlen($b)) { return strcmp($a, $b); } return (strlen($a) < strlen($b)) ? -1 : 1;'); 
    usort($words, $sort_by_strlen); 
    // We have to assume that each string has something in common with the first 
    // string (post sort), we just need to figure out what the longest common 
    // string is. If any string DOES NOT have something in common with the first 
    // string, return false. 
    $longest_common_substring = array(); 
    $shortest_string = str_split(array_shift($words)); 

    while (sizeof($shortest_string)) { 
     array_unshift($longest_common_substring, ''); 
     foreach ($shortest_string as $ci => $char) { 
      foreach ($words as $wi => $word) { 
       if (!strstr($word, $longest_common_substring[0] . $char)) { 
        // No match 
        break 2; 
       } // if 
      } // foreach 
      // we found the current char in each word, so add it to the first longest_common_substring element, 
      // then start checking again using the next char as well 
      $longest_common_substring[0].= $char; 
     } // foreach 
     // We've finished looping through the entire shortest_string. 
     // Remove the first char and start all over. Do this until there are no more 
     // chars to search on. 
     array_shift($shortest_string); 
    } 
    // If we made it here then we've run through everything 
    usort($longest_common_substring, $sort_by_strlen); 
    return array_pop($longest_common_substring); 
} 

I he escrito esto un poco en mi blog:

• Find the longest common substring using PHP (24 Feb 2011)

Answer 6

he acaba de escribir una función de los hallazgos la cadena más larga sub en str1 que existe en str2

public static function getLongestMatchingSubstring($str1, $str2) 
{ 
    $len_1 = strlen($str1); 
    $longest = ''; 
    for($i = 0; $i < $len_1; $i++){ 
     for($j = $len_1 - $i; $j > 0; $j--){ 
      $sub = substr($str1, $i, $j); 
      if (strpos($str2, $sub) !== false && strlen($sub) > strlen($longest)){ 
       $longest = $sub; 
       break; 
      } 
     } 
    } 
    return $longest; 
}