素集合データ構造のソースを表示

'''素集合データ構造'''（そしゅうごうデータこうぞう、[[英語|英]]: disjoint-set data structure）は、データの[[集合]]を[[素集合]]（互いにオーバーラップしない集合）に分割して保持する[[データ構造]]。このデータ構造に対する以下の2つの便利な操作を'''Union-Findアルゴリズム'''と呼ぶ。
* ''Find'': 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
* ''Union'': 2つの集合を1つに統合する。
これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。これら以外の重要な操作として ''MakeSet''がある。これは、与えられた1つの要素だけを格納した集合（シングルトン）を作成する。これら3つの操作により、様々な実用的[[分割問題]]を解くことができる（「応用」の節を参照）。

これらの操作をより正確に定義するには、集合の表現方法を決める必要がある。典型的な手法としては、それぞれの集合について、ある固定の要素を選択して「代表 (representative)」とし、その集合全体を表すものとする。すると ''Find''(x) は ''x'' が属する集合の代表を返す。また、''Union'' は2つの代表を引数とする。

== 素集合連結リスト ==
素集合データ構造を生成する単純な手法としては、集合毎に[[連結リスト]]を生成する方法がある。リストの先頭の要素がその集合の代表となる。

''MakeSet''は1要素のリストを生成する。''Union''は2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、''Find''が[[ランダウの記号|Ω]](n)または線形時間を必要とする点である。

これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。つまり、''Find''の引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭（代表）がわかる。しかし、このように実装すると今度は''Union''操作で各ノードの先頭へのポインタを更新しなければならなくなり、[[ランダウの記号|Ω]](n) の時間がかかるようになる。

各リストの長さがわかっているなら、短い方を長い方に連結することで''Union''の性能を改善できる。これ (''weighted-union heuristic'') を採用すると、''n''個の要素について、''m''回の''MakeSet''、''Union''、''Find''操作を行ったときにかかる時間は O(''m'' + ''n''log ''n'') となる<ref name="IntroductionToAlgorithms">Thomas H. Cormen, Charles E. Leiserson, [[ロナルド・リベスト|Ronald L. Rivest]], and Clifford Stein. ''Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp.498&ndash;524.</ref>。漸近的により高速な操作には別のデータ構造が必要である。

== 素集合森 ==
素集合森 (disjoint-set forest) はそれぞれの集合を[[木構造 (データ構造)|木構造]]で表したデータ構造で、各ノードには親ノードへの[[参照 (情報工学)|参照]]がある。1964年、Bernard A. Galler と Michael J. Fischer が考案したが<ref>Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. ''Communications of the ACM,'' Volume 7, Issue 5 (May 1964), pages 301-303. 素集合森に関する最初の論文。 [http://portal.acm.org/citation.cfm?doid=364099.364331 ACM Digital Library]</ref>、詳細な解析にはその後何年かかかった。

素集合森では、各集合の代表は木構造の根となる。''Find''は親ノードへのリンクを根に到達するまでたどっていく。''Union''は2つの木構造を1つにする操作であり、どちらかの根が全体の根となる。以下に素集合森の実装例を[[擬似コード]]で示す。

  '''function''' MakeSet(x)
      x.parent := x
  
  '''function''' Find(x)
      '''if''' x.parent == x
         '''return''' x
      '''else'''   
         '''return''' Find(x.parent)
  
  '''function''' Union(x, y)
      xRoot := Find(x)
      yRoot := Find(y)
      xRoot.parent := yRoot

この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。しかし、これを改善する方法が2つある。

第一の方法は ''union by rank'' と呼ばれ、''Union''操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するには''rank'' を用いる。これは、1要素の木の rank を 0 とし、同じ rank ''r'' の木を連結したとき、全体の根とした方の木の rank を ''r''+1 とするものである。このようにするだけで、''MakeSet''、''Union''、''Find'' 操作の償却実行時間は <math>O(\log n)</math> となる。改良した <code>MakeSet</code> と <code>Union</code> の擬似コードは以下のようになる。

  '''function''' MakeSet(x)
      x.parent := x
      x.rank   := 0
  
  '''function''' Union(x, y)
      xRoot := Find(x)
      yRoot := Find(y)
      '''if''' xRoot.rank > yRoot.rank
          yRoot.parent := xRoot
      '''else if''' xRoot.rank < yRoot.rank
          xRoot.parent := yRoot
      '''else if''' xRoot != yRoot ''// x と y が同じ集合にない場合だけマージする。
          yRoot.parent := xRoot
          xRoot.rank := xRoot.rank + 1

第二の改善は ''path compression'' と呼ばれ、''Find''操作を行ったときに構造を平坦化するものである。''Find''で根ノードまでのリンクをたどっているとき、各ノードは同じ代表を共有しているので、それらを根ノードに直接接続できる。このため、<code>Find</code> は再帰的にたどったノードが全て親ノードとして根ノードを指すように変更する。こうすると木構造はより平坦になり、その後の操作が高速化される。以下に <code>Find</code> の改良版を示す。

  '''function''' Find(x)
      '''if''' x.parent == x
         '''return''' x
      '''else'''
         x.parent := Find(x.parent)
         '''return''' x.parent

これらの手法は相補的であり、これを共に行うことで各操作の償却実行時間は <math>O(\alpha(n))</math> となる。ここで <math>\alpha(n)</math> は関数 <math>f(n) = A(n,n)</math> の逆であり、<math>A</math> は非常に高速に大きな値になる[[アッカーマン関数]]である。<math>\alpha(n)</math> はその逆関数なので、実用的な <math>n</math> の値に対しては常に 5 未満の値になる。したがって、各操作の償却実行時間は事実上非常に小さな定数となる。

実際、これは[[漸近最良]]である。Fredman と Saks は1989年、どのような素集合データ構造でも1回の操作あたり平均で <math>\Omega(\alpha(n))</math> のノードにアクセスするとした<ref>[[:en:Michael Fredman|M. Fredman]] and M. Saks. The cell probe complexity of dynamic data structures. ''Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing'', pages 345&ndash;354. May 1989. "Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires &Omega;(''m'' &alpha;(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets."</ref>。

== 応用 ==
素集合データ構造は[[集合の分割]]をモデル化したもので、例えば無向[[グラフ理論|グラフ]]の[[連結グラフ|連結成分]]などに対応する。したがって、2つの頂点が同じ成分に属するかどうかを調べたり、新たな辺を追加することで[[サイクル (グラフ理論)|閉道]]となるかを調べるのに利用できる。

[[Boost|Boost Graph Library]] では、[http://www.boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components] 機能の実装に素集合データ構造を使っている。また、グラフの最小[[全域木]]を求める[[クラスカル法]]の実装にもこれを使っている。

なお、素集合森の実装では削除ができない点に注意されたい。上述した2つの改良を施しても削除は容易ではないが、削除に対応したもっと複雑な手法が既に設計されている<ref>Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems, ''ACM Computing Surveys,'' Volume 23, Issue 3 (September 1991), pages 319-344. [http://portal.acm.org/citation.cfm?id=116878 ACM Digital Library]</ref>。

== 歴史 ==
素集合森は考案されてからよく使われていたが、上限（そして限定的な下限）が[[アッカーマン関数]]の逆関数であることを証明したのは[[ロバート・タージャン]]だった。それまで、操作毎の時間の上限は[[ジョン・ホップクロフト]]と[[ジェフリー・ウルマン]]が証明した O(log<sup>*</sup> n) とされていた。log<sup>*</sup> は[[重複対数]]であり、これも増加の遅い関数である（ただし、アッカーマン関数の逆関数ほどではない）。タージャンと van Leeuwen はより効率的なワンパスの ''Find'' のアルゴリズムも考案している。

2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre が素集合森データ構造の[[永続データ構造|永続]]版を発表した。これは構造の以前のバージョンを効率的に保持するもので、[[計算機支援証明]]システム[[Coq]]を使って形式的に正しさが証明されている<ref>Sylvain Conchon and Jean-Christophe Filliâtre. A Persistent Union-Find Data Structure. In ACM SIGPLAN Workshop on ML, Freiburg, Germany, October 2007.</ref>。

== 脚注・出典 ==
{{Reflist}}

== 外部リンク ==
* [http://www.emilstefanov.net/Projects/DisjointSets.aspx C++ and C# implementations], by Emil Stefanov
* [http://www.boost.org/libs/disjoint_sets/disjoint_sets.html C++ disjoint sets implementation], part of the [[Boost|Boost C++ libraries]]
* [http://www.cs.unm.edu/~rlpm/499/uf.html Java applet: A Graphical Union-Find Implementation], by Rory L. P. McGuire
* ''[http://citeseer.ist.psu.edu/anderson94waitfree.html Wait-free Parallel Algorithms for the Union-Find Problem]'', a 1994 paper by Richard J. Anderson and Heather Woll - ブロックすることなく並列化したUnion-Findの実装について

{{データ構造}}

{{DEFAULTSORT:そしゆうこうてえたこうそう}}
[[Category:データ構造]]
[[Category:償却データ構造]]