5

Algorithm Design Manualでは、それは言う

2 つのツリーが同型かどうかをテストしていますか? – ツリーや平面グラフなど、特定のグラフ同形の特殊なケースでは、より高速なアルゴリズムが存在します。おそらく、最も重要なケースは、ツリー間の同型を検出することです。これは、言語パターン マッチングおよび解析アプリケーションで発生する問題です。構文木は、テキストの構造を記述するためによく使用されます。基礎となるテキストのペアが同じ構造を持つ場合、2 つの構文木は同形になります。

Tree Isomorphism を使用して言語パターン マッチングの問題を解決する方法の例を教えてください。つまり、言語パターン マッチングをツリー同型問題にどのようにマッピングできますか?

通常、文字列またはテキストをツリーとして構築し、それらの同一性を比較するにはどうすればよいでしょうか?

ありがとう

4

2 に答える 2

4

例として英語を使用すると、いくつかの英語の文は次の構文木で表すことができるという考えがあります。

        SENTENCE               SENTENCE
       /        \             /        \
  PROPER NOUN  VERB      COMMON NOUN  VERB
      /                    /    \
     NAME                ARTICLE NOUN

英語のフレーズ「犬が吠える」。次に、次のように解析できます

ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

    COMMON NOUN
     /      \
ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks


            SENTENCE
             /     \
    COMMON NOUN     \
     /      \        \
ARTICLE    NOUN      VERB
 /          /         /
The       dog       barks

同じ構造の別の文は「葉が落ちる」です。その構文木は同じ形をしているように見えます。つまり、2 つの構文木は同形です。つまり、意味は異なりますが、文として同じ論理構造を持っています。

            SENTENCE
             /     \
    COMMON NOUN     \
     /      \        \
ARTICLE    NOUN      VERB
 /          /         /
A         leaf      falls

実際の物理的な単語を無視すると、両方の解析ツリーも一般的なパターンと同型であり、ツリーとして表されます。

于 2012-05-08T05:09:35.163 に答える
0

本文に示されているように、解析ツリーがここでの重要な概念です。解析ツリーはテキストの構造を (何らかの方法で) 表し、技術的にはツリーであるため、任意のツリー アルゴリズムを使用して解析ツリーを操作できます。

解析ツリーは、正式な文法に従って文字列の構文構造を表す、順序付けられたルート ツリーです。

(パースツリーに関するウィキペディアの記事)

于 2012-05-07T21:48:02.967 に答える