バラの木

コンピューティングにおいて、ローズツリーとは、ノードごとに可変かつ無制限の数のブランチを持つツリーデータ構造の値を指す用語です。 ^{[1]この用語は主に関数}型プログラミングコミュニティで、たとえばバード・メルテンス形式主義のコンテキストで使用されます。^[2]多分岐特性とは別に、ローズツリーの最も重要な特性は、双相似性が同一性と一致することです。つまり、2つの異なるローズツリーが双相似になることはありません。

「バラの木」という名前は、似た名前で似た構造を持つ一般的なシャクナゲを連想させるために、ランバート・メーレンスによって造られた。^[3]

このような木を、ロドデンドロン（ギリシャ語のῥόδον = バラ、δένδρον = 木）の直訳であるバラの木と呼ぶことにします。これは、この低木の姿に似ているためです。ただし、ロドデンドロンが北半球で逆さまに成長することはありません。

適切に構築されたローズツリーは、次のタイプのエンティティの再帰的な構築によって定義できます。

1. 基本エンティティは、定義済みの値の基本集合V（「先端」値^[3]） の要素です。
2. 分岐エンティティ (または、フォーク エンティティまたはフォレスト エンティティ) は、次のいずれかのサブタイプです。
   1. エンティティの セット。
   2. エンティティの シーケンス。
   3. 定義済みの名前のセットΣからエンティティへの 部分的なマップ。

   (a)(b)(c) はいずれも空になることがあります。(b) は (c) の特殊なケースと見なすことができることに注意してください。つまり、シーケンスは自然数の集合の最初のセグメントからのマップにすぎません。 ${\displaystyle \mathbb {N} }$

3. ペアリングエンティティは、 Fが分岐エンティティであり、xが「ラベル」値の定義済みセットLの要素である順序付きペア（F、x）です。ペアリングエンティティは、そのコンポーネントとして分岐エンティティのみを含むことができるため、分岐エンティティのサブタイプに対応するサブタイプ（3a）、（3b）、または（3c）への誘導分割があります。

通常、構築にはエンティティ タイプのいくつかの組み合わせのみが使用されます。元の論文^[3]では、1+2b (「シーケンス フォーク」ローズ ツリー) と 1+2a (「セット フォーク」ローズ ツリー) のみが考慮されています。後の文献では、1+2b バリアントは通常、次の定義によって導入されます。

データ ツリー a = リーフ a | ノード [ツリー a]

ローズツリーは、値を含む葉、または任意のサブツリーのリストを持つことができるノードのいずれかです。 ^[4]

関数型プログラミング（特にHaskell ）で最もよく使われる定義は、3+2b を組み合わせたものです。

データ ローズα = ノードα [ローズα]

Rose αの要素は、ラベル付きノードとサブツリーのリストで構成されます。 ^[1] つまり、バラの木は、分岐エンティティがバラの木のシーケンス（つまりタイプ2b）であるペアリングエンティティ（タイプ3）です。

場合によっては、1+3bの組み合わせも考慮されます。^{[5] [6]} 次の表は、最も確立されたエンティティの組み合わせの概要を示しています。

注:

一般的なバラの木は、ノードと矢印に適切なラベルをつけたアクセス可能な尖ったマルチダイグラフの双相似性によって定義できます。これらの構造は、非整集合論のアクセス可能な尖ったグラフ(略してapg )の概念を一般化したものです。以下で説明するマルチダイグラフ構造には、頭字語apq を使用します。これは、「アクセス可能な尖った quiver」の略語です。quiverは、「マルチダイグラフ」の確立された同義語です。

再帰定義で使用されるエンティティのタイプに対応して、apqの各ノードにはタイプ(1)、(2a)、(2b)、(2c)、または(3)が割り当てられます。apqは、再帰的に構築されたエンティティの特性を模倣する条件に従います。

1. 1. タイプ(1)のノードは、定義済みの基底値集合Vの要素である。
   2. タイプ(1)のノードは矢印のソースとして表示されません。
2. 1. タイプ(3)のノードは、正確に1つの矢印のソースとして表示されます。
   2. (a)で述べた矢印のターゲットはタイプ(2)のノードである。
3. タイプ(2a)の同じソースノードを持つ2つの異なる矢印には、異なるターゲットがあります。
4. ノードは、そのタイプが(3)である場合にのみラベルが付けられる。ラベルは定義済み集合Lに属する。
5. 1. 矢印のソースノードがタイプ(2b)の場合、 矢印にはインデックスが付けられます。${\displaystyle \mathbb {N} }$
   2. 矢印のソースノードがタイプ(2c)である場合、 矢印には定義済みセットΣ の名前が付けられます。
   3. それ以外の場合、矢印にはラベルが付きません。
6. 同じソース ノードを持つ矢印のラベルは異なります。
7. 同じソースノードを持つ矢印のラベル(2b)型は、の初期セグメントを形成します。 ${\displaystyle \mathbb {N} }$

apqs 𝒳 = ( X , ...)と𝒴 = ( Y , ...)間の双類似性は、 𝒳と𝒴のルートがRに関連しており、 Rに関連するノードのすべてのペア( x , y )に対して、次の条件が満たされるような ノード間の 関係R ⊆ X × Yです。

1. ノードxとy は同じタイプです。
2. xとyが型(1)の 場合、それらは同一です。
3. xとyが型(3)の 場合、それらは同じラベルを持ちます。
4. 𝒳の 矢印a（始点がx）に対しては、 𝒴の矢印b（始点がy）が存在し、
   1. aとb のターゲットノードはR関連であり、
   2. aとb のラベルは、定義されている場合は同一です。

   𝒳と𝒴 を交換すると対称条件が満たされます。

2 つの apq 𝒳と𝒴 は、それらに双相似関係Rが存在する場合、双相似であると言われます。これにより、すべての apq のクラスに同値関係が確立されます。

バラの木は、与えられたapq 𝒳と双相似なapqのクラス𝒞の固定された表現です。𝒳のルートノードがタイプ(1)の場合、 𝒞 = {𝒳 }となり、𝒞はこのルートノードで表現できます。それ以外の場合、𝒞 は適切なクラスです。この場合、表現はスコットのトリックによって、 𝒞の最低ランク の要素の集合として提供できます。

上記の集合論的構成の結果として、定義構成要素としての集合V (基底値)、Σ (矢印名)、およびL (ノード ラベル) に応じて、すべてのバラの木のクラスℛが定義されます。その後、 apqs の構造は、 ℛ上のラベル付き多重ダイグラフ構造に引き継がれます。つまり、ℛの要素自体は、誘導されたタイプの割り当て、ノードのラベル付け、および矢印を持つ「ノード」と見なすことができます。矢印のクラス𝒜は、 (ℛ × ℛ) ∪ (ℛ × ( ∪ Σ ) × ℛ)のサブクラスです。つまり、矢印は、ソースのタイプに応じて、ソース-ターゲット カップルまたはソース-ラベル-ターゲット トリプルのいずれかになります。 ${\displaystyle \mathbb {N} }$

ℛのすべての要素rに対して、 r が𝒳のルートノードであり、 𝒳 のノードと矢印のそれぞれのセットXとAが、rから始まる矢印のパスを介してアクセスできるℛと𝒜の要素によって形成されるような、誘導された apq 𝒳 = ( X 、 A 、 r 、...)があります。誘導された apq 𝒳 は、 rの構築に使用される apqs と双相似です。

集合分岐ノードを含まないローズツリー (タイプ 2a) は、パス名マップで表すことができます。パス名は、矢印ラベルの有限シーケンスにすぎません。矢印パスa → = [ a ₁ , ..., a _n ] (連続する矢印の有限シーケンス) の場合、pのパス名は、矢印ラベルの対応するシーケンス σ ( a → ) = [ σ ( a ₁ ), ..., σ ( a _n )]です 。ここでは、各矢印にラベルが付けられていると想定しています ( σ はラベル付け関数を示します)。一般に、各矢印パスは、ペアリングノード (タイプ 3) をソースとするすべての矢印を削除することによって最初に縮小される必要があります。

パス名pが解決可能であるのは、パス名がp であるルート起点矢印パスa →が存在する場合のみです。このような→は、ラベルなしの最後の矢印（ペアリング ノードをソースとする）に一意に与えられます。空でない解決可能なパスのターゲット ノードは、ラベルなし矢印で終わらない、対応するルート起点矢印パスの最後の矢印のターゲット ノードです。空のパスのターゲットはルート ノードです。

集合分岐ノードを含まないバラの木rが与えられた場合、 rのパス名マップは、次の一般的なスキームに従って、 解決可能な各パス名pにその値t ( p )を割り当てるマップtです。

∪ Σは矢印ラベルの集合 (は自然数の集合、Σは矢印名の集合) 、 Lはノードラベルの集合、V は基底値の集合であることを思い出してください 。追加の記号⊥とT はそれぞれ、解決可能なパス名のインジケータと型タグの集合 ( T = {'1', '2b', '2c', '3b', '3c' })を意味します。tマップは、次の規定によって定義されます ( x はpのターゲットを表します)。 ${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$

異なるローズ ツリーには異なるパス名マップがあることが示されています。「同質の」ローズ ツリーの場合、タイプ タグ付けは必要なく、パス名マップtは以下のように定義できます。

いずれの場合も、パス名に関して単純な公理化が存在します。

1. dom( t ) は、 ^⁎またはΣ ^⁎の空でないプレフィックス閉じた部分集合です。 ^⁎の場合、dom( t ) はツリードメインを形成するために「左兄弟閉じ」である必要があります。シーケンスによるエンコードを参照してください。${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$
2. ネストされたリストまたはネストされた辞書値の場合、pがdom( t )内で最大でないパス名であれば、t ( p )=⊥となる。^{[p 2]}

特に、最も一般的な「Haskell」の意味でのバラの木は、自然数の有限シーケンスの空でないプレフィックス閉かつ左兄弟閉集合から集合Lへの単なる写像です。このような定義は、関数型プログラミングの分野以外で主に使用されます。ツリー (オートマトン理論)を参照してください。通常、この定義を使用するドキュメントでは、「バラの木」という用語はまったく使用されません。

注:

以下の図は、対応するHaskellコードとともにローズツリーの2つの例を示しています。どちらの場合も、Haskellコンテナパッケージ^{[12]で提供されているData.Treeモジュール[11]}が使用されています。 このモジュールは、次の定義によってペアリングエンティティとしてローズツリーを導入します。

データTree a = Node { rootLabel :: a , -- ^ ラベル値subForest :: [ Tree a ] -- ^ 0 個以上の子ツリー}     
                   
              
    

両方の例は、バラの木の際立った特徴である「サブ構造の共有」 ^[13]の概念を示すために考案されています。 どちらの場合も、ラベル付け関数は単射（ラベル'a'、'b'、'c'または が'd'サブツリー/ノードを一意に識別する）であり、これは一般に満たされる必要はありません。 矢印に沿った自然数（0、1、2、または 3）は、subForest特定の「スーパーツリー」のシーケンスでツリーが出現するゼロベースの位置を示します。 の繰り返しの可能性があるためsubForest、ノード間に複数の矢印が存在する可能性があります。 各例で、問題のバラの木は によってラベル付けされ'a'、コード内の変数の値に等しくなりますa。 両方の図で、ツリーはソースのない矢印によってポイントされます。

Data.Treeをインポートしますmain :: IO () main = do let d = Node { rootLabel = 'd' , subForest = [] } let c = Node { rootLabel = 'c' , subForest = [ d ] } let b = Node { rootLabel = 'b' , subForest = [ d , c ] } let a = Node { rootLabel = 'a' , subForest = [ b , c , c , c ] } print a 
   
  
           
           
           
           
 

Data.Treeをインポートしますmain :: IO () main = do let root x = case x of 'a' -> ( x ,[ x , 'b' ]) '​​b' -> ( x ,[ x , 'c' ]) '​​c' -> ( x ,[ x , 'a' ]) let a = unfoldTree root 'a' putStrLn ( take 900 ( show a ) ++ " ... (以下同様)" ) 
   
  
      
       
       
       
     
    
   

a最初の例は、増分構築によって得られたwell-founded rose tree を示しています。最初にdが構築され、次に がc構築されb、最後に が構築されますa。rose tree は、左側に示すパス名マップによって表すことができます。

a2 番目の例は、幅優先コンストラクタによって構築された非整基盤ローズ ツリーを示していますunfoldTree。ローズ ツリーはムーア マシンです (上記の注記を参照)。パス名マップ t  : {0,1} ^⁎ → {'a','b','c' } は、t ( p )がn  mod 3に従ってそれぞれ'a'または'b'または'c'に等しくなるように定義されます( nはp内の1の出現回数) 。

一般的な定義は、ツリー データ構造への接続を提供します。

ローズツリーは双相似性を法とするツリー構造です。

「ツリー構造」とは、各ノードに一意の矢印パスでアクセスできる apq (一般的な定義ではマルチダイグラフとラベル付けされています) です。すべてのバラの木は、このようなツリー構造と双相似であり (すべての apq はその展開と双相似であるため)、このようなツリー構造はすべて、正確に 1 つのバラの木と双相似であり、したがって、そのバラの木はツリー構造の 値と見なすことができます。

右の図は、このような構造から値へのマッピングの例を示しています。図の上部には、23 個のノードを含む、ノードラベル付きの順序付きツリー Tが表示されています。下部には、 Tの値であるローズツリーRが表示されています。( TとRの両方で、兄弟矢印は暗黙的に左から右に順序付けられています。) 青い矢印で部分的に表示されている誘導されたサブツリーからサブ値へのマッピングがあります。

マッピングは多対一であることに注意してください。つまり、異なるツリー データ構造が同じ値を持つことができます。特定の結果として、一般にバラの木は、そのサブ値間の「サブ値」関係の点ではツリーではありません。#Terminological_controversy を参照してください。

上記の値のマッピングを使用すると、「ツリー データ構造」と「ツリー データ型」という用語の違いを明確にすることができます。

ツリーデータ型は、ツリーデータ構造の値のセットです。^{[dt 1]}

これらの用語の間には 2 度の相違があることに注意してください。これは、単一のツリー データ型と単一のツリー データ構造を比較すると明らかになります。単一のツリー データ型には (無限に) 多数の値が含まれており、それぞれの値は (無限に) 多数のツリー データ構造によって表されます。

たとえば、ラベルの集合L = {'a','b','c','d' } が与えられた場合、ラベルがLから取得された Haskell の意味でのバラの木の集合 (3b) は、単一の木のデータ型です。上記のバラの木の例はすべてこのデータ型に属します。

注:

上記のテキストと図からわかるように、「バラの木」という用語は議論を呼んでいます。相互に関連する問題が 2 つあります。

1. 「ノード」の意味が不明瞭です。
2. 「ツリー」と「サブ構造の共有」の間の矛盾。

興味深いことに、「ノード」という用語は、20ページの非公式な段落で「ノード」が1回だけ使用されている以外、元の論文^[3]には登場しません。後の文献では、この単語は頻繁に使用されています。これは、定義に対する引用コメントですでに確認できます。

• バラの木は [...] 葉 [...] または節 [...] のいずれかです。 ^[4]
• Rose αの要素はラベル付きノード[...]で構成されます。 ^[1]

特に、最も一般的な Haskell の意味におけるバラの木の定義は、(議論の文脈内では)「ノード」と「ツリー」が同義語であることを示唆しています。これは、すべてのバラの木がそのルート ノードと一致することを意味しますか? そうである場合、そのようなプロパティはバラの木に固有のものと見なされますか、それとも他のツリーにも適用されますか? このような質問は未回答のままです。

(B)の問題は、上記の例の図を見ると明らかです。どちらの図も、各ノードが正確に1回描かれているという意味で忠実です。基礎となるグラフが木ではないことがすぐにわかります。木（グラフ理論）からの引用を使用すると、

コンピュータ サイエンスでツリーと呼ばれるさまざまな種類のデータ構造には、グラフ理論のツリーである基礎グラフがあります [...]

一般的にバラの木は、コンピュータ科学で知られている通常の意味での木ではないと結論付けることができます。

コンピュータ サイエンスでは、「サブ構造の共有」が排除される「ローズ ツリー」という用語が少なくとも 1 つ採用されています。ベイジアン ローズ ツリーの概念は、次のローズ ツリーの定義に基づいています。

Tがバラの木であるとは、あるデータポイントxに対してT = {x }であるか、またはT = { T ₁ , ... , T _{n T} }である場合である。ここで、T _iはデータポイントの互いに素な集合上のバラの木である。 ^[14]