encontrar la mayoría de las cadenas repetidas sub en orden

Question

tengo una matriz:

$myArray=array(

'hello my name is richard', 
'hello my name is paul', 
'hello my name is simon', 
'hello it doesn\'t matter what my name is' 

); 

Necesito encontrar la subcadena (mínimo 2 palabras) que se repite con más frecuencia, tal vez en un formato de matriz, por lo que mi regreso matriz podría tener este aspecto:

$return=array(

array('hello my', 3), 
array('hello my name', 3), 
array('hello my name is', 3), 
array('my name', 4), 
array('my name is', 4), 
array('name is', 4), 

); 

por lo que puedo ver en esta matriz de matrices con qué frecuencia se repite cada cadena entre todas las cadenas de la matriz.

es la única manera de hacerlo de esta manera? ..

function repeatedSubStrings($array){ 

    foreach($array as $string){ 
     $phrases=//Split each string into maximum number of sub strings 
     foreach($phrases as $phrase){ 
      //Then count the $phrases that are in the strings 
     } 
    } 

} 

He intentado una solución similar a la anterior pero era demasiado lento, el procesamiento de alrededor de 1000 filas por segundo, ¿alguien puede hacerlo ¿Más rápido?

Answer 1

Una solución a esto podría ser

function getHighestRecurrence($strs){ 

    /*Storage for individual words*/ 
    $words = Array(); 

    /*Process multiple strings*/ 
    if(is_array($strs)) 
     foreach($strs as $str) 
     $words = array_merge($words, explode(" ", $str)); 

/*Prepare single string*/ 
    else 
     $words = explode(" ",$strs); 

    /*Array for word counters*/ 
    $index = Array(); 

    /*Aggregate word counters*/ 
    foreach($words as $word) 

      /*Increment count or create if it doesn't exist*/ 
      (isset($index[$word]))? $index[$word]++ : $index[$word] = 1; 


    /*Sort array hy highest value and */ 
    arsort($index); 

    /*Return the word*/ 
    return key($index); 
} 

Answer 2

Supongo que por "subscring" realmente quiere decir "división de subcadenas a lo largo de límites de palabras" ya que eso es lo que muestra su ejemplo.

En ese caso, asumiendo que cualquier subcadena máxima repetida servirá (ya que puede haber vínculos), siempre puede elegir una sola palabra como una subcadena máxima repetida, si lo piensa. Para cualquier frase "A B", las frases "A" y "B" individualmente deben ocurrir al menos tan frecuentemente como "A B" porque ambas ocurren cada vez que "A B" lo hace y pueden ocurrir en otros momentos. Por lo tanto, una sola palabra debe tener un recuento que al menos se relacione con cualquier subcadena que contenga esa palabra.

Así que solo tiene que dividir todas las frases en un conjunto de palabras únicas, y luego simplemente contar las palabras y devolver una de las palabras con el recuento más alto. Esto ejecutará manera más rápida que en realidad contar todas las posibles subcadenas.

Answer 3

Esto debería funcionar en O (n)

$twoWordPhrases = function($str) { 
    $words = preg_split('#\s+#', $str, -1, PREG_SPLIT_NO_EMPTY); 
    $phrases = array(); 
    foreach (range(0, count($words) - 2) as $offset) { 
     $phrases[] = array_slice($words, $offset, 2); 
    } 
    return $phrases; 
}; 
$frequencies = array(); 
foreach ($myArray as $str) { 
    $phrases = $twoWordPhrases($str); 
    foreach ($phrases as $phrase) { 
     $key = join('/', $phrase); 
     if (!isset($frequencies[$key])) { 
      $frequencies[$key] = 0; 
     } 
     $frequencies[$key]++; 
    } 
} 
print_r($frequencies); 

Answer 4

Si bien esto tiene un tiempo de ejecución más alto, creo que es más simple desde el punto de vista puesta en práctica:

$substrings = array(); 

foreach ($myArray as $str) 
{ 
    $subArr = explode(" ", $str); 
    for ($i=0;$i<count($subArr);$i++) 
    { 
     $substring = ""; 
     for ($j=$i;$j<count($subArr);$j++) 
     { 
      if ($i==0 && ($j==count($subArr)-1)) 
       break;  
      $substring = trim($substring . " " . $subArr[$j]); 
      if (str_word_count($substring, 0) > 1) 
      { 
       if (array_key_exists($substring, $substrings)) 
        $substrings[$substring]++; 
       else 
        $substrings[$substring] = 1; 
      } 
     } 
    } 
} 

arsort($substrings); 
print_r($substrings);