Дисјунктни-сет (структура података)

MakeSet creates 8 singletons.

After some operations of Union, some sets are grouped together.

Дисјунктни-сет је структура података која прати скуп елемената подељена у велики број дисјунктних (непреклапајућих) подскупова. Алгоритам за проналажење скупова је алгоритам који обавља две корисне операције на такве структуре података:

Пронађи: Одређује у ком се подскупу налази неки елемент. Ово може да се користи за одређивање да ли су два елемента у истом подскупу.
Унија: Спаја два подскупа у један подскуп.

Још једна битна операција је НаправиСкуп, која прави скуп који се састоји од задајућег елемента, другачије назван „синглтон“. У циљу прецизније дефинисати ове операције, потребан је неки начин представљања. Један уобичајен приступ је да изаберете фиксни елемент сваког скупа, који ће бити представник тог скупа, да представља скуп као целину. Затим, Пронађи(к) враћа представника скупа у ком се налази к, а Унија узима представнике два скупа као своје аргументе.

Историја

Док су идеје које су се користиле у дисјунктивним-сет шумама дуго били познате, Robert Tarjan је био први који је доказао горње границе (и ограничена верзију доње границе) у смислу инверзности Ackermann function, 1975.^[1] До тода, најбоља граница за време по операцији, доказано од стране Hopcroft и Ullman,^[2] био је доказ O(log^* n) , итеративни алгоритам од n, још једна споро растућа функција(али не спора колико и инверзна Ackermann function).

Tarjan и Van Leeuwen су такође развили један Нађи алгоритам који је ефикаснији у пракси али задржава нагору комплексност.^[3]

Године 2007, Sylvain Conchon и Jean-Christophe Filliâtre су развили упорну структуру података persistent верзија структуре података дисјунктних-сет шума, омогућавајући претходну верзију структуре да се ефикасно задрже, формализовају његову исправност користећи доказ proof assistant Coq.^[4]

Дисјунктни-сет у повезаним листама

Једноставан приступ креирању Дисјунктни-сет структури је да се створи повезана листа за сваки скуп. Елемент на челу сваке листе је изабран за свог представника. НаправиСкуп креира листу једног елемента. Унија спаја две листе. Недостатак овога је да је операција Пронађи захтева линеарно време, пролази листу уназад од датог елемента на врху листе. Ово се може избећи, укључујући у сваком чвору повезане листе показивач на почетак (чело) листе. Онда је операцији Пронађи потребно константно време, јер овај показивач показује директно на представника скупа. Међутим, Унија сада мора да ажурира сваки елемент у листи и сада је њој потребно линеарно време.

Дисјунктни-сет шуме

Ово су структуре података где је сваки скуп представљен дрветом (струкуром података) у којој сваки чвор држи референцу на свог родитеља. Њих су први пут описали Бернард А. Гали и Мичаел Ј. Фисчер 1964. године. Представник сваког сета је корен стабла тог скупа је. Операција Нађи следи родитељске чворове док не стигне до корена. Унија комбинује два стабла у једно прикључивањем корена једног корену другог стабла. Један од начина имплементације може бити следећи:

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

У овом наивном облику, овај приступ није ништа бољи од приступа повезаних листа, јер дрво може да буде веома неуравнотежено; међутим, може се побољшати на два начина. Први начин који се зове унија по ранковима је да се увек мање дрво надовезује на корен већег дрвета. У контексту овог алгоритма, термин ранк се користи уместо дубине. Дрвећа са једним елементом су дефинисана да им је ранк 0 и када год се два дрвета која имају исти ранк „р“ споје, резултат ранка је „р+1". Само применом ове технике најгоре време извршавања је О(лог н) за било коју од 3 наведене операције (НаправиСкуп, Унија или Пронађи). Псеудокод:

function MakeSet(x)

     x.parent := x
     x.rank   := 0

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x and y are not already in same set. Merge them.
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

Ове две технике комплеметнирају једна другу. Прмењују се заједно време за рад је само $O(\alpha (n))$ , where $\alpha (n)$ is the inverse of the function $n=f(x)=A(x,x)$ , and $A$ екстремно брзо расте Ackermann function. Пошто $\alpha (n)$ је обрнуто од ове функције, $\alpha (n)$ је мање од 5 за све даљине практичне вредности $n$ . Дакле, време извршавања по операцији је ефикасно мала константа.

У ствари, ово је асимптотски оптималан : Fredman и Saks су показали 1989. да <матх> \ омега (\ алпха (н)) </ матх> речи морају бити приступљене било ком дисјунктном-скупу структура података по операцији у просеку^[5]

Примена

Примена дисјунктивног-сета структура података модела подела скупа partitioning of a set, је на пример да пратите повезане компоненте (connected components) неусмереног графа (undirected graph). Овај модел се затим може користити за одређивање да ли две гране припадају истом чвору, или да ли ће додавање границе између њих резултовати у циклусом. Унија-Нађи алгоритам се користи у имплементацијама високих перформанси Unification.^[6]

Референце

^ Tarjan, Robert Endre (1975). „Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215—225. doi:10.1145/321879.321884.
^ Hopcroft, J. E.; Ullman, J. D. (1973). „Set Merging Algorithms”. SIAM Journal on Computing. 2 (4): 294—303. doi:10.1137/0202024.
^ Tarjan, Robert E.; van Leeuwen, Jan (1984), „Worst-case analysis of set union algorithms”, Journal of the ACM, 31 (2): 245—281
^ Conchon, Sylvain; Filliâtre, Jean-Christophe (октобар 2007), „A Persistent Union-Find Data Structure”, ACM SIGPLAN Workshop on ML, Freiburg, Germany
^ Fredman, M.; Saks, M. (мај 1989), „The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345—354, „Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.”
^ Knight, Kevin (1989). „Unification: A multidisciplinary survey”. ACM Computing Surveys. 21: 93—124. doi:10.1145/62029.62030.

Спољашње везе

C++ implementation, part of the Boost C++ libraries
A Java implementation with an application to color image segmentation, Statistical Region Merging (SRM), IEEE Trans. Pattern Anal. Mach. Intell. 26(11): 1452–1458 (2004)
Java applet: A Graphical Union–Find Implementation, by Rory L. P. McGuire
Wait-free Parallel Algorithms for the Union–Find Problem Архивирано на сајту Wayback Machine (18. јул 2008), a 1994 paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union–Find that never needs to block
Python implementation
Visual explanation and C# code

[1] Tarjan, Robert Endre (1975). „Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM. 22 (2): 215—225. doi:10.1145/321879.321884.

[2] Hopcroft, J. E.; Ullman, J. D. (1973). „Set Merging Algorithms”. SIAM Journal on Computing. 2 (4): 294—303. doi:10.1137/0202024.

[3] Tarjan, Robert E.; van Leeuwen, Jan (1984), „Worst-case analysis of set union algorithms”, Journal of the ACM, 31 (2): 245—281

[4] Conchon, Sylvain; Filliâtre, Jean-Christophe (октобар 2007), „A Persistent Union-Find Data Structure”, ACM SIGPLAN Workshop on ML, Freiburg, Germany

[5] Fredman, M.; Saks, M. (мај 1989), „The cell probe complexity of dynamic data structures”, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345—354, „Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.”

[6] Knight, Kevin (1989). „Unification: A multidisciplinary survey”. ACM Computing Surveys. 21: 93—124. doi:10.1145/62029.62030.

[1]

[2]

[3]

[4]

[5]

[6]