эффективно находить перекрывающиеся сегменты из набора списков

Question

Предположим, я вызываю следующие списки:

[1, 2, 3, 20, 23, 24, 25, 32, 31, 30, 29] [1, 2, 3, 20, 23, 28, 29] [1, 2, 3, 20, 21, 22] [1, 2, 3, 14, 15, 16] [16, 17, 18] [16, 17, 18, 19, 20]

вопросы здесь порядок. Это узлы, полученные в результате поиска по глубине в взвешенном графе. То, что я хочу сделать, это разбить списки на уникальные пути (где путь имеет не менее 2 элементов). Таким образом, вышеуказанные списки будут возвращать следующее:

[1, 2, 3] [20, 23] [24, 25, 32, 31, 30, 29] [28, 29] [20, 21, 22] [14, 15, 16] [16, 17, 18] [19, 20]

Основная идея у меня сейчас это:

1. Посмотри все пары списков, чтобы создать набор списков перекрытия сегменты в начале списка. Например, в приведенном выше примере, это будет выход:
   [1, 2, 3, 20, 23] [1, 2, 3, 20] [1, 2, 3] [16, 17, 18]

2. Следующий вывод будет таким:
   [1, 2, 3] [16, 17, 18]

3. После того, как у меня есть списки, начиная с шага 2, я смотрю через каждый список входных и отрубить фронт, если он совпадает с одним из списков с шага 2. новые списки выглядеть следующим образом:
   [20, 23, 24, 25, 32, 31, 30, 29] [20, 23, 28, 29] [20, 21, 22] [14, 15, 16] [19, 20]

4. я затем вернуться и применить шаг 1 к усеченным списки фр om step 3. Если на шаге 1 не отображаются какие-либо перекрывающиеся списки, я готов.

Шаг 2 - сложная часть здесь. Что глупо, это на самом деле эквивалентно решению исходной проблемы, хотя и в меньших списках.

Что является наиболее эффективным способом решения этой проблемы? Глядя на все пары, очевидно, требуется время O (N^2), а шаг 2 кажется расточительным, так как мне нужно выполнить ту же процедуру для решения этих меньших списков. Я пытаюсь выяснить, есть ли более разумный способ сделать это, и я застрял.

Answer 1

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

Спасибо за помощь всем!

Answer 2

Похоже, решение состоит в том, чтобы модифицировать Trie для достижения цели. Сжатие Trie дает подсказки, но тип сжатия, который здесь необходим, не принесет никаких преимуществ.

Первый добавленный вами список становится его собственным узлом (а не узлами k). Если есть какое-либо перекрытие, узлы разбиваются, но никогда не становятся меньше, чем удерживают два элемента массива.

Простой пример структуры графа выглядит следующим образом:

insert (1,2,3,4,5) 
graph: (1,2,3,4,5)->None 
insert (1,2,3) 
graph: (1,2,3)->(4,5), (4,5)->None 
insert (3,2,3) 
graph: (1,2,3)->(4,5), (4,5)->None, (3,32)->None 
segments 
output: (1,2,3), (4,5), (3,32) 

Дочерние узлы также должны быть добавлены в качестве фактического TRIE, по крайней мере, когда их достаточно, чтобы избежать линейного поиска при добавлении/удаление из структуры данных и потенциальное увеличение времени выполнения по коэффициенту N. Если это будет реализовано, структура данных будет иметь такую ​​же большую производительность O, как и Trie с несколько более высокими скрытыми константами. Это означает, что для этого требуется O (L * N), где L - средний размер списка, а N - количество списков. Получение сегментов является линейным по числу сегментов.

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

Обратите внимание, что эта структура данных может быть построена по мере запуска DFS, а не после слов.