21

潜在的に無限のシンボルのセットがあります:A, B, C, ...明確な特別なプレースホルダー シンボルもあります?(その意味は以下で説明します)。

すべてのノードにシンボルがアタッチされ、0 個以上の空でないサブツリーがあるような、空でない有限ツリーを検討してください。特定のノードのサブツリーの順序は重要です (したがって、たとえば、2 つのサブツリーを持つノードがある場合、どちらが左でどちらが右であるかを区別できます)。任意のシンボルは、異なるノードに接続されたツリーに 0 回以上表示できます。プレースホルダ シンボル?は、リーフ ノード (つまり、サブツリーを持たないノード) にのみ付けることができます。ツリーが非循環であることは、ツリーの通常の定義から導き出されます。

有限性要件は、ツリー内のノードの総数が正の有限整数であることを意味します。添付されたシンボルの総数、ツリーの深さ、およびすべてのサブツリーのノードの総数はすべて有限です。

ツリーは関数表記法で与えられます。ノードはそれに付けられた記号で表され、サブツリーがある場合は、同じ方法で再帰的に表されるサブツリーのカンマ区切りのリストを含む括弧が続きます。だから、例えば木

                    A
                   / \
                  ?   B
                     / \
                    A   C
                   /|\
                  A C Q
                       \
                        ?

として表されA(?,B(A(A,C,Q(?)),C))ます。

一致するパターンとして使用される、事前に計算された不変のツリーSのセットがあります。通常、セットには ~ 10 5のツリーがあり、そのすべての要素には通常 ~ 10 ～ 30 のノードがあります。以下に述べる私の問題に最も適したSの表現を事前に作成するのに十分な時間を費やすことができます。

ツリーT (通常は ~ 10 2ノード)を受け入れ、TがサブツリーとしてSの要素を含むかどうかを可能な限り高速にチェックする関数を作成する必要があります。TまたはSの要素に?現れる場合の両方)。

セットSを格納するデータ構造と一致をチェックするアルゴリズムを提案してください。任意のプログラミング言語または疑似コードで問題ありません。

4

2 に答える 2

6

この論文では、有限状態機械 (標準の Aho-Corasick アルゴリズムが文字列マッチングに使用する) を使用する代わりに、アルゴリズムがサブツリー マッチングにプッシュダウン オートマトンを使用する、 Aho-Corasick アルゴリズムの変形について説明します。Aho-Corasick 文字列マッチング アルゴリズムと同様に、そのバリアントは、入力ツリーを 1 回通過するだけで、 Sの辞書全体と照合する必要があります。

この論文は非常に複雑です。著者に連絡して、利用可能なソース コードがあるかどうかを確認する価値があるかもしれません。

于 2013-06-16T04:24:05.890 に答える
4

必要なのは、潜在的な一致のセットを追跡する有限ステート マシンです。

本質的に、そのようなマシンは、パターンを相互に照合し、個々の一致のどの部分が共有されているかを判断した結果です。これは、レクサーがトークンの正規表現のセットを取得し、文字を 1 つずつ処理することによって任意の正規表現に一致できる大きな FSA にそれらを構成する方法に似ています。

これを行うためのメソッドへの参照は、rewriting systems という用語の下にあります。

于 2013-06-16T04:28:52.833 に答える