1

ノードにラベルが付けられている（ただし一意ではない）ツリーのコレクションがあります。具体的には、ツリーは解析された文のコレクションからのものです（http://en.wikipedia.org/wiki/Treebankを参照）。コレクションから最も一般的なサブツリーを抽出したいと思います。パフォーマンスは（まだ）問題ではありません。ツリーバンク用にこれを行うアルゴリズム（理想的にはJava）またはツールへのポインターに感謝します。子ノードの順序が重要であることに注意してください。

@mjvを編集します。私たちは定型化された言語を持つ限られた領域（化学）で作業しているので、木の多様性はそれほど大きくありません-おそらく子供の読者に似ています。「猫がマットの上に座った」のシンプルな木。

<sentence>
  <nounPhrase>
    <article/>
    <noun/>
  </nounPhrase>
  <verbPhrase>
    <verb/>
    <prepositionPhrase>
      <preposition/>
      <nounPhrase>
        <article/>
        <noun/>
      </nounPhrase>
    </prepositionPhrase>
  </verbPhrase>
</sentence>

ここで、文には2つの同一の品詞サブツリーが含まれています（実際のトークン「cat」。「mat」はマッチングでは重要ではありません）。したがって、アルゴリズムはこれを検出する必要があります。すべてのnounPhraseが同一であるとは限らないことに注意してください-「大きな黒い猫」は次のようになります。

      <nounPhrase>
        <article/>
        <adjective/>
        <adjective/>
        <noun/>
      </nounPhrase>

文の長さは長くなります-15から30ノードの間。1000本の木から有益な結果が得られると期待しています。これに1日以上かからない場合は、許容範囲です。

明らかに、ツリーが短いほど頻繁になるため、nounPhraseが非常に一般的になります。

編集これがツリーを平坦化することによって解決される場合、私はそれが最長共通部分列ではなく最長共通部分文字列に関連していると思います。ただし、必ずしも最長のものが必要なわけではないことに注意してください。「興味深い」（基準はまだ決定されていません）のに十分な長さのリストが必要です。

4

4 に答える 4

4

コレクション内で最も頻繁に使用されるサブツリーを見つけて、サブツリーのコンパクトな形式を作成し、すべてのサブツリーを繰り返し、ハッシュセットを使用してそれらの出現を数えます。30 ノードは完全なハッシュには大きすぎます。ノードあたり約 1 ビットしかなく、兄弟か子かを示すにはそれだけの量が必要です。

その問題は LCS ではありません。最も一般的なシーケンスは、最長の共通サブシーケンスとは関係ありません。最も頻度の高いサブツリーは、最も多く発生するサブツリーです。

長さ L の N ツリーの場合、最悪の場合 O(NL^2) になるはずです (L ノードを含むサブツリーのテストの等価性が O(L) であると仮定します)。

于 2009-11-06T12:50:40.643 に答える
3

これはコンピュータサイエンスでよく知られている問題であり、効率的な解決策があります。

関連する参考資料は次のとおりです。

阿部健二、川曽根真司、浅井達也、有村博紀、有川節夫、半構造データの最適化された部分構造発見、Proc。データベースにおける知識発見の原則と実践に関する第6回欧州会議（PKDD-2002）、LNAI 2431、Springer-Verlag、1-14、2002年8月。

Mohammed J. Zaki、森林で頻繁に樹木を効率的に採掘する、第8回ACM SIGKDD国際会議、知識発見とデータマイニング、2002年7月。

または、高速なコードが必要な場合は、ここにアクセスしてください： FREQT （xmlをS式に変換しても、それほど問題は発生しないはずです。読者の練習問題として残しておきます）

于 2010-05-18T03:57:33.470 に答える
3

パフォーマンスはまだ問題ではないとおっしゃっていますが、これは NP 困難な問題であるため、決して高速化できない可能性があると思います。私の理解が正しければ、これは最長共通部分列問題の変形であると考えることができます。ツリーを次のような直線シーケンスに平坦化する場合

(nounphrase)(DOWN)(article:the)(adjective:big)(adjective:black)(noun:cat)(UP)

その後、問題は LCS になります。

Wikibooks には、LCS の Java 実装があります。

于 2009-11-06T12:21:30.080 に答える
1

この場合、gspan というツールが非常に便利であることがわかりました。http://www.cs.ucsb.edu/~xyan/software/gSpan.htmから無料でダウンロードできます。matlab インターフェイスを備えたその c++ バージョンは、http: //www.nowozin.net/sebastian/gboost/ にあります。

于 2014-04-16T10:26:18.670 に答える