поиск общих поддеревьев в дереве

Question

Рассмотрим эту концептуальную диаграмму ниже, которая предназначена только для демонстрационных целей.

   Abc       Foo
     \       /   \
      \     /     Foo2
        Bar        \
      /    \       Foo3
     Bar2   Bar3     \
     /   \           Foo4
     X    Y

В приведенном выше дереве есть уникальный «путь», Foo-> Bar-> Bar2-> X.Этот путь отличается от Abc-> Bar-> Bar2-> X .. Очевидно, что эта информация теряется в представлении выше, но учтите, что у меня есть все индивидуальные уникальные пути.часть пути "Bar-> Bar2-> X".

Цель алгоритма, который я пытаюсь найти или реализовать, состоит в том, что я хотел бы объединить эту информацию, чтобы я не мог хранить отдельные пути,Но что еще более важно, я пытаюсь найти все эти общие пути и дать им вес.Так, например, в приведенном выше случае, я мог бы сжать информацию о «Bar-> Bar2-> X» и сказать, что это произошло 2 раза.Очевидно, я бы потребовал, чтобы это работало для всех случаев.

И да, конечная идея состоит в том, чтобы быстро задать вопрос «Покажите мне все отличные пути от Foo».В этом примере есть только 1, Foo-> Bar-> Bar2-> X.Foo-> Bar-> Bar2-> Y и Foo-> Bar-> Bar3 не существуют.Диаграмма только для просмотра.

Есть идеи?

Answer 1

Так что это только отправная точка, я надеюсь, что другие помогут мне заполнить, но я буду думать о них как о строках и рассматривать общие подпуть как проблему общих подстрок, которая рассматривалась в прошлом довольно часто.Вдобавок ко всему, я мог бы инвертировать каждый путь / строку, а затем построить из них структуру trie, потому что затем, посчитав количество ключей ниже заданного узла, вы сможете увидеть, сколько раз этот конечный путь используется ... Возможно, естьлучший и более эффективный способ, но это должно работать.У кого-нибудь еще есть идеи относиться к ним как к строкам?

Answer 2

Вы можете хранить каждый уникальный путь отдельно.Чтобы ответить на такие вопросы, как «кто делает Foo вызов», вы можете создать индекс в виде хэш-таблицы.

В качестве альтернативы вы можете попробовать использовать DAWG , ноЯ не уверен, насколько это поможет в вашем случае.