algorithm - 在树中找到常见的子树

考虑下面这个概念图，它只用于演示。

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

在上面的树中，有一个唯一的“路径”，foo->bar->bar2->x。这个路径不同于abc->bar->bar2->x。显然这些信息在上面的表达式中丢失了，但是考虑到我已经存储了所有单独的唯一路径。
但是，它们共享路径“Bar->Bar2->X”的某些部分。
我试图查找或实现的算法的目的是，我希望聚合此信息，以便无法存储单个路径。但更重要的是，我试图找到所有这些共同的路径，并赋予它们权重。例如，在上面的例子中，我可以压缩关于“bar->bar2->x”的信息，并说它发生了两次。显然我会要求它适用于所有的情况。
是的，最终的想法是能够快速地提出问题“向我展示所有与foo不同的路径”。在这个例子中只有1个，FoO-> bar > BAR2-> X.FoO-> bar > BAR2-> Y和FoO-> bar > BAR3不存在。此图仅供查看。
有什么想法吗？

最佳答案

所以这只是一个起点，我希望其他人能帮我填充，但我会把它们看作字符串，把公共子路径看作是公共子串问题，这在过去已经被研究过很多次了在我的头顶上，我可以反转每个路径/字符串，然后从中构建一个trie结构，因为通过计算给定节点下的键数，可以看到该结束路径被使用了多少次……也许有更好、更有效的方法，但这应该奏效还有人想把他们当成线人吗？

关于algorithm - 在树中找到常见的子树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9553149/