Элементы быстрой кластеризации PHP, хранящиеся в массиве

У меня есть массив, состоящий из 1,5 миллионов пар элементов (разделенных ' '):

$array {
    [0] => "element1 element2"
    [1] => "element2 element3"
    [2] => "element8 element4"
    [3] => "element8 element5"
    [4] => "element4 element5"
    [5] => "element6 element7"
    [6] => ... 
}

Каждая пара элементов уникальна, а элементы представляют собой строки от 15 до 20 символов.

В моем конвейере этот массив означает [0] "элемент1 связан с элементом2", [1] "элемент2 связан с элементом3",... Я хотел бы сгруппировать вместе все связанные элементы и получить результат, аналогичный:

 $array_output {
      [0] => "element1 element2 element3"
      [1] => "element8 element4 element5"
      [2] => "element6 element7"
      [3] => ... 
 }

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


php graph-algorithm clique
person zwonoROM    schedule 25.02.2015    source источник
comment
Я не считаю эту задачу простой и не знаю очевидного способа сделать это. Я бы, вероятно, предложил взорвать пространство, а затем создать вложенную иерархическую структуру. Затем напишите что-нибудь, чтобы объединить эту структуру в нужные группы.   -  person Jonathan Kuhn    schedule 25.02.2015
comment
Я бы очень не хотел делать это в памяти PHP с таким большим количеством пар и вместо этого обрабатывать его в базе данных   -  person Mark Baker    schedule 25.02.2015
comment
Я не думаю, что это так уж проблематично. Если я неправильно понял вопрос, это можно сделать за O (n) времени и пространства, где n — количество пар во входных данных (см. мой ответ).   -  person gandaliter    schedule 25.02.2015
comment
Быстро... PHP, ты, должно быть, шутишь. Очевидно, что PHP не считается быстрым, особенно если у вас сложные алгоритмы и структуры данных.   -  person Has QUIT--Anony-Mousse    schedule 26.02.2015
comment
Кроме того, ваша проблема не определена. Вам нужны подключенные компоненты или клики? Для них нужны совсем другие алгоритмы (но вы не найдете ни того, ни другого в качестве кластеризации)   -  person Has QUIT--Anony-Mousse    schedule 26.02.2015

Ответы (1)


arrow_upward
0
arrow_downward

У вас есть граф, представленный в виде списка смежности, и вы хотите преобразовать его в список связанных компонентов графа. Лучший способ сделать это — построить наборы связанных узлов и объединить их для каждого ребра, пока у вас не останется ребер.

Чтобы сделать это в PHP:

  1. Преобразуйте свой ввод в многомерный массив ([["element1", "element2"],["element2","element3"]] и т. д.)
  2. Инициализировать список узлов в представлении карты, где каждый узел указывает на набор, содержащий только этот узел (например, ["element1" => ["element1"],"element2" => ["element2"]] и т. д.).
  3. Для каждой пары в массиве из (1) объединить наборы двух элементов в массиве из (2) и указать оба элемента, а также любые другие элементы в наборе, на вновь объединенный набор
  4. Поместите все наборы из (3) в набор (множеств), чтобы получить каждый только один раз.
  5. Преобразуйте каждый набор в желаемый выходной формат

Вы захотите использовать оператор ссылки (&), чтобы повторно использовать одни и те же массивы в (3). Алгоритм было бы намного проще реализовать на Java или чем-то еще с более очевидными хэш-картами и хэш-таблицами.

person gandaliter    schedule 25.02.2015
comment
Большое спасибо за ваше предложение. Но я боюсь, что не понимаю вашего пункта 2 «инициализировать представление карты». У вас есть пример кода? Спасибо. - person zwonoROM; 25.02.2015
comment
Идея []s заключалась в том, чтобы показать массивы (я знаю, что это не так, как они выглядят в PHP, но их легче увидеть). Все, что вы действительно делаете на шаге 2, — это создаете список узлов. Каждый из элементов должен быть в нем ровно один раз и независимо от каких-либо пар. - person gandaliter; 25.02.2015