11

ツリー構造の検索と変更に相当する正規表現はありますか? 簡潔なミニ言語 (perl regex など) は、私が探しているものです。

これは、私が探しているものを明確にするかもしれない例です。

<root>
  <node name="1">
    subtrees ....
  </node>
  <node name="2">
    <node name="2.1">
     data
    </node>
    other subtrees...
  </node>
</root>

上記のツリーで可能な操作は、「ノード 2.1 のサブツリーをノード 1 のサブツリーに移動する」です。操作の結果は次のようになります。

<root>
  <node name="1">
    subtrees ....
    <node name="2.1">
     data
    </node>
  </node>
  <node name="2">
    other subtrees...
  </node>
</root>

少なくとも 2 つの子を持つすべてのノードを検索する、データが "a" で始まるすべてのノードを検索し、サブツリーに少なくとも 2 つの他の兄弟がある場合はそれを "b" に置き換えるなどの検索および置換操作をサポートする必要があります。

唯一の次元が文字列の長さを横切る文字列の場合、正規表現を使用して上記の操作 (またはそれらの 1D 相当) の多くを実行できます。木に相当するものがあるのだろうか。(単一の正規表現の代わりに、一連の変換ルールを記述する必要があるかもしれませんが、それは問題ありません)。

いくつかの単純なミニ言語があるかどうかを知りたいです（正規表現自体ではなく、ライブラリなどを介して正規表現と同じくらいアクセスできるもの..）。これらの操作を実行するには？できれば、python ライブラリとして。

4

7 に答える 7

8

スタンフォード大学の TSurgeon と Tregex はそれを行うことができます。ライブラリはhttp://nlp.stanford.edu/software/tregex.shtmlからダウンロードできます。

于 2011-05-21T13:40:55.173 に答える
5

それができる汎用言語はわかりませんが、XPathのようなものを探しているようです。

于 2009-05-17T18:17:02.567 に答える
5

パターンベースのツリー書き換えにはTXLがあります。

パターンによるツリーの書き換えも、 ANTLRなどのパーサー ツールキットを使用して行われます。

ボトムアップ ツリー書き換えによるコード生成、Google BURS または BURG。

于 2009-05-17T18:17:31.427 に答える
1

二分探索木をナビゲートするには、状態 (どのノードにいるのか?) と比較 (その値がそれより小さいか大きいか?) が必要ですが、これは有限状態オートマトンでは実行できません。

確かに、特定の値を持つノードを検索することはできますが、たとえば、親がわからない場合に葉ではないノードを削除するにはどうすればよいでしょうか?

また、ノードから提供される情報によって親がわかっている場合でも、左のサブツリーの最小値をどのように決定し、それを削除してノードに配置するのでしょうか?

あなたは金融庁に要求しすぎていると思います。

于 2009-05-17T18:13:22.010 に答える
1

この記事では、再帰的な Perl の正規表現について興味深いヒントをいくつか提供していますが、正直なところ、ツリー構造がこのようにアプローチされることはめったにありません。

より一般的には、正規表現を使用してツリー内の特定の各ノードを解析するステート マシン スタイルのパーサーを作成します。

Expatはおそらく良い例です。

于 2009-05-17T18:17:55.310 に答える
1

Scala、F#、Erlang、Haskell (他にもあると思います) などの言語によって提供されるパターン マッチングは、ツリーなどのデータ構造を簡潔に操作するように設計されています。

これは、パターン マッチングが Scala でできることの非常に高いレベルのビューです。示されている例は、実際にはパターン マッチングの正義を行っていません。

ウィキペディアにも、パターン マッチングに関するリファレンスがいくつかあります。こことここ。

于 2009-05-17T18:33:12.820 に答える
1

XSLTが答えとして出てこないことに少し驚いています。確かに、それは特に洗練された言語ではないと思います。既存のソリューションのほとんどは、パターン マッチングよりも手続き型のアプローチを好む傾向があります。また、XML が XML に適用されているという理由だけで、やみくもに適用されることから非常に悪い評判を得ています。それは法案に適合します。残念ながら、その標準的な表現は非常に冗長ですが...

于 2009-05-17T20:51:00.407 に答える