分離集合データ構造

コンピュータサイエンスにおいて、分離集合データ構造は、和集合検索データ構造または併合検索集合とも呼ばれ、互いに素な（重複しない）集合のコレクションを格納するデータ構造です。同様に、集合を互いに素な部分集合に分割したものを格納します。新しい集合の追加、集合の併合（和集合で置き換える）、集合の代表メンバーの検索などの操作を提供します。最後の操作により、任意の 2 つの要素が同じ集合に属しているか、異なる集合に属しているかを効率的に判断できます。

分離集合データ構造を実装する方法はいくつかありますが、実際には、分離集合フォレストと呼ばれる特定の実装と同一視されることが多いです。この特殊なタイプのフォレストは、和集合および検索操作をほぼ一定の償却時間で実行します。n個のノードを持つ分離集合フォレストでのm 個の加算、和集合、または検索操作のシーケンスの場合、必要な合計時間はO ( m α( n ) ) です。ここで、α( n )は極めてゆっくりと増加する逆アッカーマン関数です。分離集合フォレストでは操作ごとにこの時間が保証されるわけではありませんが、各操作で構造のバランスが再調整されるため (ツリー圧縮によって)、後続の操作が高速になります。結果として、分離集合フォレストは漸近的に最適であり、実質的に効率的です。

分離集合データ構造は、グラフの最小全域木を見つけるためのクラスカルのアルゴリズムで重要な役割を果たします。最小全域木の重要性は、分離集合データ構造がさまざまなアルゴリズムをサポートすることを意味します。さらに、これらのデータ構造は、特にレジスタ割り当ての問題に対して、記号計算やコンパイラーで応用されています。

分離集合フォレストは、1964 年にBernard A. GallerとMichael J. Fischerによって初めて説明されました^。[2] 1973 年に、その時間計算量はの反復対数に制限され、 HopcroftとUllmanによって制限されました。^[3] 1975 年に、Robert Tarjan は、アルゴリズムの時間計算量の(逆アッカーマン関数) 上限を初めて証明しました。 ^[4]彼はまた、それが厳密であることを証明しました。1979 年に、彼はこれが Galler-Fischer 構造を含む特定のクラスのアルゴリズムの下限であることを示しました。^[5] 1989 年に、FredmanとSaks は、 (償却) ビットのワードは、任意の分離集合データ構造によって操作ごとにアクセスされる必要があることを示しました。 ^[6]${\displaystyle O(\log ^{*}(n))}$${\displaystyle n}$${\displaystyle O(m\alpha (n))}$${\displaystyle \Omega (\alpha (n))}$${\displaystyle O(\log n)}$

1991年にガリルとイタリアーノは分離集合のデータ構造の調査を発表しました。^[7]

1994年、リチャード・J・アンダーソンとヘザー・ウォルは、ブロックする必要のないUnion-Findの並列化バージョンを説明しました。^[8]

2007 年、シルヴァン・コンションとジャン＝クリストフ・フィリアトルは、分離集合フォレスト データ構造の半永続バージョンを開発し、証明支援ツール Coq を使用してその正しさを形式化しました。^[9]「半永続」とは、構造の以前のバージョンが効率的に保持されるが、データ構造の以前のバージョンにアクセスすると、それ以降のバージョンが無効になることを意味します。彼らの最速の実装は、非永続アルゴリズムとほぼ同じ効率のパフォーマンスを実現します。彼らは複雑さの分析を実行しません。

制限されたクラスの問題に対してより優れたパフォーマンスを発揮する分離集合データ構造の変種も検討されている。ガボウとタージャンは、可能な結合が特定の方法で制限されている場合、真に線形時間アルゴリズムが可能であることを示した。^[10]

分離セット フォレストの各ノードは、ポインターと、サイズまたはランク (両方ではない) などの補助情報で構成されます。ポインターは、親ポインター ツリーを作成するために使用されます。親ポインター ツリーでは、ツリーのルートではない各ノードがその親を指します。ルート ノードを他のノードと区別するために、親ポインターには、ノードへの循環参照やセンチネル値などの無効な値が含まれます。各ツリーはフォレストに格納されているセットを表し、セットのメンバーはツリー内のノードです。ルート ノードはセットの代表を提供します。2 つのノードが同じセットに含まれるのは、そのノードを含むツリーのルートが等しい場合のみです。

フォレスト内のノードは、アプリケーションにとって都合の良い方法で保存できますが、一般的な手法は、配列に保存することです。この場合、親は配列インデックスで示されます。配列の各エントリには、親ポインター用にΘ(log n )ビットのストレージが必要です。エントリの残りの部分には同等かそれより少ない量のストレージが必要なので、フォレストを保存するのに必要なビット数はΘ( n log n )です。実装で固定サイズのノードを使用する場合 (これにより、保存できるフォレストの最大サイズが制限されます)、必要なストレージはnに比例します。

分離セット データ構造は、新しい要素を含む新しいセットの作成、特定の要素を含むセットの代表の検索、および 2 つのセットのマージという 3 つの操作をサポートします。

このMakeSet操作により、新しい要素のみを含む新しいセットに新しい要素が追加され、新しいセットがデータ構造に追加されます。データ構造がセットのパーティションとして表示される場合、このMakeSet操作により新しい要素が追加されてセットが拡大し、新しい要素のみを含む新しいサブセットに新しい要素を配置することで既存のパーティションが拡張されます。

分離セット フォレストでは、MakeSetノードの親ポインターとノードのサイズまたはランクを初期化します。ルートが自分自身を指すノードによって表される場合、要素の追加は次の疑似コードを使用して記述できます。

関数MakeSet( x )は、
    x がフォレスト内にまだ存在しない場合 はx .parent := x x .size := 1      // ノードがサイズを格納する場合x .rank := 0      // ノードがランクを格納する場合end if end function
        
        
        
    

この操作には線形時間計算量があります。特に、n個のノードを持つ分離集合フォレストを初期化するにはO ( n ) 時間が必要です。

ノードに親が割り当てられていない場合、そのノードはフォレスト内に存在しないことを意味します。

実際には、x をMakeSet保持するためにメモリを割り当てる操作が先行する必要があります。メモリ割り当てが、適切な動的配列実装の場合のように、償却定数時間操作である限り、ランダムセットフォレストの漸近的なパフォーマンスは変わりません。

この操作は、指定されたクエリ ノードxからルート要素に到達するまでFind親ポインターのチェーンをたどります。このルート要素はxが属するセットを表し、 x自体である場合もあります。 到達したルート要素を返します。 Find

操作を実行するとFind、フォレストを改善する重要な機会が生まれます。Find操作の時間は親ポインターを追跡するのに費やされるため、ツリーがフラットになるとFind操作が高速になります。 がFind実行されると、各親ポインターを順にたどるよりもルートに到達するのに速い方法はありません。ただし、この検索中にアクセスされた親ポインターは、ルートに近い位置を指すように更新できます。ルートへの途中でアクセスされたすべての要素は同じセットの一部であるため、フォレストに格納されているセットは変更されません。ただし、Findクエリ ノードとルートの間のノードだけでなく、その子孫に対しても、将来の操作が高速になります。この更新は、分離セット フォレストの償却パフォーマンス保証の重要な部分です。

Find漸近的に最適な時間計算量を達成するアルゴリズムはいくつかあります。パス圧縮と呼ばれるアルゴリズムの 1 つのファミリでは、クエリ ノードとルートの間のすべてのノードがルートを指すようになります。パス圧縮は、次のように単純な再帰を使用して実装できます。

関数Find( x )は、 
    x .parent ≠ xの場合 、x .parent := Find( x .parent
     )
        を返し、そうでない場合はxを返します。 
         
         
    

この実装では、ツリーを上るパスと下るパスの 2 つのパスが実行されます。クエリ ノードからルートまでのパスを格納するのに十分なスクラッチ メモリが必要です (上記の疑似コードでは、パスはコール スタックを使用して暗黙的に表されます)。両方のパスを同じ方向に実行することで、メモリを一定量に減らすことができます。定数メモリの実装では、クエリ ノードからルートまで 2 回ウォークします。1 回はルートを見つけるため、もう 1 回はポインターを更新するためです。

関数Find( x )は
    root  := xですが、 
    root .parent ≠ rootの場合、  root  := root .parent
    が終了します。 
        

     x .parent ≠ root の
        場合、parent  := x .parent
         x .parent := root 
        x  := parentとなり、 
    while が終了する。

     ルート
終了関数を返す

TarjanとVan Leeuwen は、Find最悪の場合の複雑さは同じままで、実際にはより効率的なワンパス アルゴリズムも開発しました。 ^[4] これらはパス分割とパス半減と呼ばれます。どちらも、クエリ ノードとルート間のパス上のノードの親ポインタを更新します。 パス分割では、そのパス上のすべての親ポインタをノードの祖父母へのポインタに置き換えます。

関数Find( x )は、
    x .parent ≠ xの場合に 
        ( x , x .parent) := ( x .parent, x .parent.parent)
    を実行し、xを返します。関数終了 
     

パスの半分化も同様に機能しますが、他のすべての親ポインターのみを置き換えます。

関数Find( x )は、
    x .parent ≠ xの場合に x .parent := x .parent.parent
         x  := x .parent
    を実行し、xを返して関数を終了します。 
        
     

この操作は、xを含むセットとy を含むセットをそれらの和集合に置き換えます。 まず、 を使用してxとy を含むツリーのルートを決定します。ルートが同じ場合は、これ以上何もする必要はありません。それ以外の場合は、 2 つのツリーをマージする必要があります。これは、xのルートの親ポインタをy のルートに設定するか、 yのルートの親ポインタをxに設定することによって行われます。 Union(x, y)UnionFind

どのノードを親にするかの選択は、ツリーに対する将来の操作の複雑さに影響します。これを不注意に行うと、ツリーが非常に高くなる可能性があります。たとえば、 が常にx をUnion含むツリーをy を含むツリーのサブツリーにするとします。要素で初期化されたばかりのフォレストから始めて、、 、 ... 、を実行します。結果のフォレストには、ルートがnである単一のツリーが含まれ、 1 からnへのパスはツリー内のすべてのノードを通過します。このフォレストの実行時間はO ( n )です。 ${\displaystyle 1,2,3,\ldots ,n,}$Union(1, 2)Union(2, 3)Union(n - 1, n)Find(1)

効率的な実装では、ツリーの高さは、サイズによる結合またはランクによる結合を使用して制御されます。 どちらの場合も、ノードは親ポインター以外の情報も保存する必要があります。 この情報は、どのルートが新しい親になるかを決定するために使用されます。 どちらの戦略でも、ツリーが深くなりすぎないようにします。

サイズによる結合の場合、ノードはそのサイズを格納します。これは単純に子孫の数 (ノード自体を含む) です。ルートxとy を持つツリーが結合されると、子孫の数が多いノードが親になります。2 つのノードの子孫の数が同じ場合は、どちらかが親になることができます。どちらの場合も、新しい親ノードのサイズは、子孫の新しい合計数に設定されます。

function Union( x , y )は
    // ノードをルートに置き換える
    x  := Find( x )
     y  := Find( y )

     x = y の場合
        return   // x と y はすでに同じ集合内にある
    end if

    
    // 必要であれば、変数を交換して、 x が少なくとも y と同じ数の子孫を持つ
    ようにします。if  x .size < y .size then 
        ( x , y ) := ( y , x )
     end if

    // x を新しいルートにする
    y .parent := x 
    // x のサイズを更新する
    x .size := x .size + y .size
関数の終了

サイズを格納するために必要なビット数は、明らかにn を格納するために必要なビット数です。これにより、フォレストに必要なストレージに定数係数が追加されます。

ランクによる結合では、ノードは高さの上限であるランクを格納します。ノードが初期化されると、ランクは 0 に設定されます。ルートxとy を持つツリーを結合するには、まずそれらのランクを比較します。ランクが異なる場合は、ランクが大きい方のツリーが親になり、xとyのランクは変わりません。ランクが同じ場合は、どちらが親になることもできますが、新しい親のランクは 1 ずつ増加します。ノードのランクは明らかに高さと関連していますが、高さを格納するよりもランクを格納する方が効率的です。ノードの高さはFind操作中に変わることがあるため、ランクを格納すると、高さを正確に保つための余分な労力を省くことができます。疑似コードでは、ランクによる結合は次のようになります。

function Union( x , y )は
    // ノードをルートに置き換える
    x  := Find( x )
     y  := Find( y )

     x = y の場合
        return   // x と y はすでに同じ集合内にある
    end if

    
    // 必要に応じて、変数名を変更して、 x のランクが y のランク以上になるよう
    にします。if  x .rank < y .rank then 
        ( x , y ) := ( y , x )
     end if

    // x を新しいルートにする
    y .parent := x 
    // 必要に応じて、x のランクをインクリメントする
    if  x .rank = y .rank then 
        x .rank := x .rank + 1
     end if 
end function

すべてのノードはランク以下であることが示されています。 ^{[11]その結果、各ランクは}O (log log n )ビット で格納でき、すべてのランクはO ( n log log n )ビットで格納できます。 これにより、ランクはフォレストのサイズの漸近的に無視できる部分になります。 ${\displaystyle \lfloor \log n\rfloor }$

上記の実装から、ノードがツリーのルートでない限り、ノードのサイズとランクは重要ではないことは明らかです。ノードが子になると、そのサイズとランクに再びアクセスされることはありません。

Findが親ポインタを更新せず、 がUnionツリーの高さを制御しない分離セットフォレスト実装では、高さがO ( n )のツリーを持つことができます。このような状況では、Findと の操作にはO ( n )時間が Union必要です。

実装がパス圧縮のみを使用する場合、 n回の 操作のシーケンスMakeSetに続いて最大n −1回の Union操作とf回の Find操作を実行すると、最悪の場合の実行時間は になります。^[11]${\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}$

ランクによる結合を使用し、実行中に親ポインタを更新しない場合、任意のタイプのm個の操作（最大n個の操作）のFind実行時間は になります。^[11]${\displaystyle \Theta (m\log n)}$MakeSet

パスの圧縮、分割、半分化と、サイズまたはランクによる結合を組み合わせると、最大n個の操作を含む任意のタイプのm個の操作の実行時間が に短縮されます。^{[4] [5]}これにより、各操作の償却実行時間 が になります。これは漸近的に最適であり、すべての分離セットのデータ構造は操作ごとに償却時間を使用する必要があります。^[6] ここで、関数は逆アッカーマン関数です。逆アッカーマン関数の増加は非常に遅いため、この係数は、物理宇宙に実際に記述できる任意のnに対して4以下になります。これにより、分離セット操作は実質的に償却定数時間になります。 MakeSet${\displaystyle \Theta (m\alpha (n))}$${\displaystyle \Theta (\alpha (n))}$${\displaystyle \Omega (\alpha (n))}$${\displaystyle \alpha (n)}$

分離集合フォレストのパフォーマンスの正確な分析はやや複雑です。しかし、n個のオブジェクトを含む分離集合フォレストに対する任意のm Findまたは操作の償却時間はO ( m log ^* n )であることを証明する、はるかに単純な分析があります。ここで、log ^*は反復対数を表します。^{[12] [13] [14] [15]}Union

補題 1: find 関数がルートまでのパスをたどるにつれて、遭遇するノードのランクが増加します。

補題2: ランクrのサブツリーのルートであるノードuには少なくともノードがある。 ${\displaystyle 2^{r}}$

補題3: ランクrのノードの最大数は、最大で${\displaystyle {\frac {n}{2^{r}}}.}$

実行中の任意の時点で、グラフの頂点をランクに応じて「バケット」にグループ化できます。バケットの範囲は、次のように帰納的に定義します。バケット 0 にはランク 1 の頂点が含まれます。バケット 1 にはランク 2 と 3 の頂点が含まれます。一般に、B番目のバケットに区間 のランクの頂点が含まれる場合、(B+1) 番目のバケットには区間 のランクの頂点が含まれます。${\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}$${\displaystyle \left[R,2^{R}-1\right].}$

については、 とします。すると、バケットには区間 内のランクを持つ頂点が存在します。 ${\displaystyle B\in \mathbb {N} }$${\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}$${\displaystyle B}$${\displaystyle [{\text{tower}}(B-1),{\text{tower}}(B)-1]}$

バケットのサイズについては 2 つの点が観察できます。

1. バケットの合計数は最大でlog ^* nです。

   証明: 頂点のランクは より大きいことはできないため、頂点を持つことができるのは最初のバケットのみです。ここで、 は上で定義した関数の逆を表します。${\displaystyle n}$${\displaystyle \log ^{*}(n)}$${\displaystyle \log ^{*}}$${\displaystyle {\text{tower}}}$

2. バケット内の要素の最大数は です。 ${\displaystyle \left[B,2^{B}-1\right]}$${\displaystyle {\frac {2n}{2^{B}}}}$

   証明: バケット内の要素の最大数は最大で${\displaystyle \left[B,2^{B}-1\right]}$${\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}$

Fは実行された「検索」操作のリストを表し 、

$${\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}$$ $${\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}$$ $${\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}$$

すると、 m個の検索にかかる総コストは${\displaystyle T=T_{1}+T_{2}+T_{3}.}$

各検索操作はルートに到達するトラバーサルを1回だけ行うため、T ₁ = O ( m )となります。

また、バケットの数に関する上記の制限から、T ₂ = O ( m log ^* n )となります。

T ₃では、 uからvへのエッジをトラバースしていると仮定します。ここで、uとv はバケット[ B、 2 ^B − 1]内でランクを持ち、v はルートではありません (このトラバースの時点では、そうでなければトラバースはT ₁で考慮されます)。u を固定し、さまざまな検索操作でvの役割を果たすシーケンスを検討します。 パス圧縮とルートへのエッジを考慮していないため、このシーケンスには異なるノードのみが含まれ、補題 1 により、このシーケンス内のノードのランクは厳密に増加していることがわかります。 両方のノードがバケット内にあるため、シーケンスの長さk (ノードuが同じバケット内の異なるルートに接続されている回数) は、最大でバケットB内のランクの数、つまり最大で${\displaystyle v_{1},v_{2},\ldots ,v_{k}}$${\displaystyle 2^{B}-1-B<2^{B}.}$

したがって、${\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}$

観察1と2から、次のように結論付けることができる。${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

したがって、${\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}$

ランクによる結合または重みによる結合を持つFind木における 操作の最悪ケースの時間は です(つまり であり、この境界は厳密です)。1985 年に、N. Blum はパス圧縮を使用せず、 の間に木を圧縮する操作の実装を示しました。彼の実装は操作あたり 時間で実行され、^[16] Galler と Fischer の構造と比較すると、操作あたりの最悪ケースの時間は短縮されますが、償却時間は短縮されます。1999 年に、Alstrup らは、逆アッカーマン償却時間とともに最適な最悪ケースの時間を持つ構造を示しました。^[17]${\displaystyle \Theta (\log n)}$${\displaystyle O(\log n)}$${\displaystyle union}$${\displaystyle O(\log n/\log \log n)}$${\displaystyle O(\log n/\log \log n)}$

通常の分離集合フォレストの実装では、要素の削除に対して好ましく反応しない。つまり、要素数の減少によって の時間は改善されない。しかし、定数時間の削除を可能にし、 の時間制限が現在の要素数に依存するFind最新の実装が存在する^{[18] [19]}Find

分離集合データ構造は集合の分割をモデル化し、例えば無向グラフの接続成分を追跡する。このモデルは2つの頂点が同じ成分に属しているかどうか、あるいはそれらの間に辺を追加すると循環になるかどうかを判定するために使用できる。Union-Findアルゴリズムは、統一の高性能な実装で使用されている。^[20]

このデータ構造は、Boost Graph Libraryによって増分接続コンポーネント機能を実装するために使用されます。また、グラフの 最小全域木を見つけるためのKruskal アルゴリズムを実装するための重要なコンポーネントでもあります。

Hoshen -Kopelman アルゴリズムでは、アルゴリズム内で Union-Find を使用します。

• パーティションの改良、つまり、ばらばらのセットを維持するための異なるデータ構造で、セットを結合するのではなく分割する更新を行う。
• ダイナミックな接続

• Boost C++ ライブラリの一部である C++ 実装
• Java実装、JGraphTライブラリの一部
• Javascriptの実装
• Python実装