Найти наиболее повторяющиеся подстроки в массиве

Question

У меня есть массив:

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

);

Мне нужно найти подстроку (минимум 2 слова), которая повторяется чаще всего, возможно, в формате массива, поэтому мой возвращаемый массив может выглядеть следующим образом:

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

);

Таким образом, из этого массива я могу видеть, как часто каждая строка повторялась среди всех строк в массиве.

Это единственный способ сделать это? ..

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

}

Я пробовал решение, подобное приведенному выше, но оно было слишком медленным, обрабатывая около 1000 строк в секунду, может кто-нибудь сделать это быстрее?

Answer 1

Решением этого может быть

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

Хотя время выполнения выше, я думаю, с точки зрения реализации это проще:

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

Answer 3

Я предполагаю, что под "подстрокой" вы на самом деле имеете в виду "подстрока, разделенная по границам слов", поскольку именно это показывает ваш пример.

В этом случае, если подойдет любая максимальная повторяющаяся подстрока (поскольку могут быть связи), вы всегда можете выбрать только одно слово в качестве максимальной повторяющейся подстроки, если вы об этом думаете. Для любой фразы «A B» фразы «A» и «B» по отдельности должны встречаться, по крайней мере, так же часто, как «A B», потому что они оба встречаются каждый раз, когда «A B» происходит, и они могут встречаться в другое время. Следовательно, одно слово должно иметь число, которое по крайней мере связано с любой подстрокой, содержащей это слово.

Так что вам просто нужно разбить все фразы на набор уникальных слов, а затем просто посчитать слова и вернуть одно из слов с наибольшим количеством. Это будет работать намного быстрее , чем фактически подсчитывать все возможные подстроки.

Answer 4

Это должно выполняться за 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);