1

オブジェクト ツリーで最大反復サブツリーを見つける問題を解決しようとしています。

オブジェクト ツリーとは、各リーフとノードに名前があるツリーを意味します。各リーフには、そのリーフに関連付けられたタイプとそのタイプの値があります。各ノードには、特定の順序でリーフ/ノードのセットがあります。

オブジェクト ツリーが与えられた場合、その中に繰り返しサブツリーがあることがわかっています。

反復とは、葉の値以外のすべて (名前/タイプ/サブ要素の順序) が類似している 2 つ以上のサブツリーを意味します。サブツリー間でノード/リーフを共有することはできません。

問題は、これらの最大高さのサブツリーを特定することです。

徹底的な検索がうまくいくことはわかっています。私はむしろより効率的なアプローチを探しています。

4

1 に答える 1

1

各ノードのハッシュ値を生成する dfs トラバーサルを実装できます。これらの値をノードの高さと一緒に単純な配列に格納します。サブツリーの候補は値が重複しています。2 つの異なるサブツリーが同じハッシュ値を生成する可能性があるため、候補に問題がないことを確認してください。
リーフと内部ノードがすべてノード型であり、標準のアクセスとトラバーサル機能が利用可能であると仮定します。

procedure dfs_update( node : Node, hashmap : Hashmap )
begin
  if is_leaf(node) then
    hashstring = concat("LEAF",'|',get_name_str(node),'|',get_type_str(node))
  else // node is an internal node
    hashstring = concat("NODE",'|',get_name_str(node))
    for each child in get_children_sorted(node)
      dfs_update(child,hashmap)
      hashstring = concat(hashstring,'|',get_hash_string(hashmap,child))
    end for
  end if
  // only a ref to node is added to the hashmap, we could also add
  // the node's height, hashstring, whatever could be useful and inapropriate
  // to keep in the Node ds
  add(hashmap, hash(hashstring),node)
end

トリッキーな部分は の後でdfs_update、高さを降順で hasmap 内の衝突ノードのリストを取得し、それらが実際に繰り返されているかどうかを 2 つずつ確認する必要があります。

于 2012-09-04T17:35:23.423 に答える