Trova più ripetuta stringhe sub in ordine di

Question

Ho un array:

$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' 

); 

ho bisogno di trovare la stringa sub (min 2 parole) che si ripete più volte, magari in formato di array, così il mio ritorno serie potrebbe assomigliare a questo:

$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), 

); 

modo che io possa vedere da questo array di array quanto spesso ogni stringa è stata ripetuta fra tutte le stringhe nella matrice.

è l'unico modo per farlo in questo modo? ..

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 
     } 
    } 

} 

ho provato una soluzione simile al precedente ma era troppo lento, l'elaborazione circa 1000 righe al secondo, chiunque può farlo Più veloce?

Answer 1

Una soluzione a questo potrebbe essere

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

Suppongo che per "sottostringa" si intende realmente "sottostringa divisa lungo i limiti delle parole" poiché questo è ciò che mostra il tuo esempio.

In tal caso, supponendo che venga eseguita una sottostringa massima ripetuta (poiché potrebbero esserci vincoli), è sempre possibile scegliere una singola parola come sottostringa massima ripetuta, se ci si pensa. Per ogni frase "A B", le frasi "A" e "B" singolarmente devono presentarsi almeno con la stessa frequenza di "A B" perché si verificano entrambe ogni volta che "A B" si verifica e possono verificarsi in altri momenti. Pertanto, una singola parola deve avere un conteggio che almeno si collega a una sottostringa che contiene quella parola.

Quindi è sufficiente dividere tutte le frasi in un insieme di parole univoche, quindi contare le parole e restituire una delle parole con il conteggio più alto. Questo verrà eseguito molto più veloce che effettivamente contando ogni sottostringa possibile.

Answer 3

Questo dovrebbe essere eseguito in 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

Anche se questo ha un tempo di esecuzione più alto, penso che sia più semplice dal punto di vista dell'attuazione:

$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);