Tìm lặp đi lặp lại hầu hết các tiểu chuỗi trong mảng

Question

Tôi có một mảng:

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

); 

tôi cần phải tìm ra chuỗi phụ (tối thiểu 2 từ) được lặp đi lặp lại thường xuyên nhất, có lẽ trong một định dạng mảng, vì vậy tôi trở lại mảng có thể trông giống như sau:

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

); 

Vì vậy, tôi có thể thấy từ mảng này tần suất mỗi chuỗi được lặp lại trong tất cả các chuỗi trong mảng.

là cách duy nhất để làm điều đó như thế này? ..

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

} 

Tôi đã thử một giải pháp tương tự như trên nhưng nó là quá chậm, xử lý khoảng 1000 hàng mỗi thứ hai, bất cứ ai có thể làm điều đó nhanh hơn?

Answer 1

Một giải pháp này có thể là

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

Tôi giả định bằng "chuỗi con", bạn thực sự có nghĩa là "phân tách chuỗi con dọc theo ranh giới từ" vì đó là ví dụ của bạn.

Trong trường hợp đó, giả định bất kỳ chuỗi con lặp lại tối đa nào sẽ làm (vì có thể có quan hệ), bạn luôn có thể chọn chỉ một từ làm chuỗi con lặp lại tối đa, nếu bạn nghĩ về nó. Đối với bất kỳ cụm từ "A B", các cụm từ "A" và "B" riêng lẻ phải xuất hiện ít nhất là "A B" vì chúng đều xuất hiện mỗi lần "A B" và chúng có thể xảy ra vào những thời điểm khác. Do đó, một từ đơn lẻ phải có số lượng ít nhất là quan hệ với bất kỳ chuỗi con nào có chứa từ đó.

Vì vậy, bạn chỉ cần chia tất cả các cụm từ thành một tập hợp các từ duy nhất, sau đó chỉ đếm các từ và trả về một trong các từ có số lượng cao nhất. Điều này sẽ chạy cách nhanh hơn hơn so với thực sự đếm mọi chuỗi con có thể.

Answer 3

này nên chạy trong thời gian O (n) thời gian

$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

Trong khi điều này có một thời gian chạy cao hơn, tôi nghĩ rằng nó đơn giản từ một quan điểm thực hiện:

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