ツリー内の共通のサブツリーを見つける

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から見せてください」という質問をすばやく聞くことができるようにすることです。この例では、Foo-> Bar-> Bar2-> Xの1つしかありません。 Foo→Bar→Bar2→Y、Foo→Bar→Bar3は存在しません。このダイアグラムは表示用です。

アイデア？

Answer 1

これは単なる出発点ですが、私が他の人が記入するのを助けてくれることを願っていますが、私は文字列として考え、共通のサブパスの問題を過去のかなりの部分で見てきました。私の頭の上から私はそれぞれのパス/文字列を逆転させ、それらからトライ構造を構築するかもしれません。そのため、与えられたノードの下のキーの数を数えることによって、より効率的な方法ですが、それはうまくいくはずです。誰もが文字列として扱うアイデアはありますか？

Answer 2

個別のパスを個別に保存することもできます。 「誰がFoo呼び出しを行うか」などの質問に答えるには、ハッシュテーブルの形式でインデックスを作成します。

DAWGを試してみることもできますが、あなたのケースでどのくらい助けてくれるか分かりません。