Fuziono stablo

Из Википедије, слободне енциклопедије

Fuziono stablo predstavlja stablo koje implementira asocijativni niz nad w-bitnim celim brojevima. Коristi O(n) prostora i izvršava pretragu u O(logw n)) vremenu, koje je asimptotski brže od tradicionalnog binarnog stabla, i u stvari bolje od van Emde Boas stable gde je w veće. To postiže brzinu eksploatacije pojedinih operacija koje imaju konstantno vreme koje je potrebno u mašinskom jeziku. Fuziono stablo su osmislili Michael Fredman and Dan Willard.[1]

Nekoliko naprednih stvari je urađeno od kad su Fredman i Vilard osmislili algoritam 1990. 1999.[2] prikazano je kako se može implementirati fuziono stablo preko AC0 modela, u čijoj implementaciji više nije potrebno konstantno vreme. Dinamička verzija fuzionog stabla koja koristi heš tabele je predložena 1996[3] koja je O(logw n) složenosti. Druga dinamička verzija koja je predložena 2007.[4] koristi eksponencijalno stablo čija je složenost u najgorem slučaju O(logw n + log log u) po operaciji, gde je u veličina najvećeg ključa. Ostaje otvoreno pitanje da li će dinamička fuzija moći da postigne složenost od O(logwn) po operaciji.

Каko radi[уреди]

Fuziono stablo je u osnovi B-stablo sa izdvajanjem faktora w1/5 (bilo koji mali eksponent dolzi u obzir), koji daje složenost O(logw n). Da bismo postigli željenju radnu verziju za ispravke i upite, fuzionim stablom moramo omogućiti da pretrazivanje čvora podrazumeva više od w1/5 ključeva u konstantnom vremenu. Ovo se može uraditi “sabijanjem” ključeva tako da se svi mogu snaći na mašinskom jeziku, što zauzvrat omogućava da se sabijanje radi paralelno. Ostatak ovog članka će opisati operacije u statičkom Fuzionom stablu, u kom su podržani samo upiti.

Skiciranje[уреди]

Skiciranje je metod koji podrazumeva da svaki w-bitni ključ u čvoru sadrži k ključeva koji su kompresovani na samo k-1 bita. Svaki ključ x može se posmatrati kao deo binarnog stabla visine w koji počinje korenom i završava se listom koji odgovara x. Da bi se razlikovala dva dela, dovoljno je pogledati u njihove tačke grananja (prvi bit gde se dva ključa razlikuju). Svi k delovi zajedno imaju k-1 tački grananja, zato je potrebno najviše k-1 bita da bi se razlikovali bilo koji od k ključeva.

FusionTreeSketch.gif

Važna uloga skiciranja je da čuva red ključeva. To je, sketch(x) < sketch(y) za bilo koja sva ključa gde je x<y.

Približna skica[уреди]

Ako je zapis kompresovanih bita b1 < b2 < ··· < br, onda je kompresovanje ključa xw-1···x1x0 r-bitnog celog broja x_{b_r}x_{b_{r-1}}\cdots x_{b_1}. Sa standardnim operacijama kakve se koriste u C jeziku, teško je direktno izračunati kompresovanje ključa u konstantnom vremenu. Umseto toga, kompresovani bitovi mogu biti zapakovani u opsegu veličine od najviše r4 , koristeći bitovsko AND i množenje. Bitovsko AND služi da ukloni sve nekompresovane bitove iz ključa, dok množenje pomera kompresovane bitove u mali niz. Kao i „savršena“ skica, skica čuva približan raspored ključeva. Za neke reči je potrebno utvrditi tačan broj umnožavanja konstanti. Svaki kompresovani bit na lokaciji bi će množenjem biti pomeren na bi + mi preko m = \textstyle\sum_{i=1}^r. Za približno skiciranje moramo se držati sledećih pravila:

  1. bi + mj su različiti za svaki par (i, j). To nam garantuje da kompresovani bitovi neće biti oštećeni prilikom množenja.
  2. bi + mj je strogo rastuća funkcija od i. To znači da je redosled kompresovanih bitova očuvan.
  3. (br + mr) - (b1 - m1) ≤ r4. To znači da su kompresovani bitovi zapakovani u opsegu veličine od r4.

Induktivni argument pokazuje kako mi može biti konstruisan. Neka je m1 = wb1. Pretpostavimo da 1 < tr i da su 'm1, m2... mt već izabrani. Onda se izabere najmanji ceo broj mt koji zadovoljava osobine (1) i (2). Osobina (1) zahteva da mtbibj + ml za sve 1 ≤ i, jr i 1 ≤ lt-1. Prema tome, postoji manje od tr2r3 koji mt mora da zadovoljava. Kad je mt izabran da bude minimum,(bt + mt) ≤ (bt-1 + mt-1) + r3. Ovo objašnjava osobinu (3).

Približan zapis se izračunava na sledeći način: 1. Maskiraju se svi kompresovani i bitovi koji su konjugovani . 2. Množenjem ključ će biti predodređen za konstantu m. Ova operacija u stvari zahteva dve mašinske reči , ali ovo i dalje može biti urađeno u konstantnom vremenu. 3. Maskira se sve, osim pomerenih kompresovanih bitova. Oni se sada smeštaju u susedni blok od najviše r4 < w4/5 bita. U nastavku ovog članka, kompresovanje će označavati približno skiciranje.

Paralelno poređenje[уреди]

Cilj kompresije je da sabijanjem dozvoli da svi ključevi budu smešteni u jednu w-bitnu reč. Onda će sabijanje čvora biti sledeći niz znakova: 1sketch(x1)1sketch(x2)...1sketch(xk) . Možemo videti da sketch funkcija koristi tačno b ≤ r4 bita. Zatim, svaki blok koristi 1 + bw4/5 bita, a od kw1/5 , ukupan broj bitova u čvoru je najviše w. Ukratko: za niz s i ne negativni broj m, sm označava ulančavanje niza s m puta. Ako je t takođe niz, st označava niz od t do s. Skiciranje čvora omogućava nam da pretrazujemo ključ za bilo koji b-bitni ceo broj y. Neka je z = (0y)k može biti izračunato i u konstantnom vremenu (množenje u konstantom (0b1)k). Napomenimo da je 1sketch(xi) - 0y uvek pozitivno, ali čuva vodeću skicu 1 iff sketch(xi) ≥ y. Mi na taj način možemo izračunati najmanji index i tako da sketch(xi) ≥ y podrazumeva

  1. Oduzimanjem z iz čvora
  2. Uzeti razlike bitovskog „I“ i konstante (10b)k. Ovo briše sve osim vodećeg bita svakog bloka.
  3. Naći najvažniji bit rezultata.
  4. Izračunati i, koristeći činjenicu da je vodeći bit i-tog bloka imamindex i(b+1).

Dekompresovanje[уреди]

Za proizvoljan upit, paralelna komparacija izračunava indeks i prema sledećoj formuli

sketch(xi-1) ≤ sketch(q) ≤ sketch(xi).

Nažalost, šema funkcije ne čuva kopiju ključeva tako da nije neophodno da xi-1qxi. Šta je tačno u tome, od svih ključeva, bilo xi-1 or xi imaju najduži zajednički prefiks sa q. To je zato što bilo koji ključ y sa dužim prefiskom istim sa q, takođe ima više zajedničkih kompresovanih bitova sa q, i sketch(q) je mnogo sličniji sketch(xj). Najduži zajednički prefiks između dva w-bitna cela broja a i b mogu biti izračunati u konstantnom vremenu, tako što se traži najznačajniji bit diskjunkcije od a i b. Ovo se može upotrebiti kao maska za sve bite sem za zajedničke prefiksne bitove. Napomenimo da p tačno definiše gde se q grananje završava.Ako je sledeći bit od q 0, onda se naslednik od q nalazi u p1 podstablu, i ako je sledeći bit od q 1, onda se predak od q nalazi u p0 podstablu. Ovo prati sledeći algoritam:

  1. Koristi se paralelna komparacija da se nađe sledeći indeks i tako da važi sketchsketch(xi-1) ≤ sketch(q) ≤ sketch(xi).
  2. Izračunava se najduzi zajednički prefiks od p i q, bilo xi-1 ili xi (uzima se duži od ova dva).
  3. Neka je l-1 dužina najdužeg zajedničkog prefiksa sa p.
    1. Ako je l-ti bit od q jednak 0, onda je e = p10w-l. Koristiti paralelnu komaparaciju da se nađe naslednik od sketch(e). To je u stvari predak od q.
    2. Ko je l-ti bit od q jednak 1, onda e = p01w-l.Koristi se komparacija da se nađe predak od sketch(e). To je u stvari naslednik od q.
  4. Kada jednom nađemo pretka ili naslednika od q, tačna pozicija q u grupi ključeva je određena.

Reference[уреди]

  1. ^ M. L. Fredman and D. E. Willard. BLASTING through the information theoretic barrier with FUSION TREES. Proceedings of the twenty-second annual ACM symposium on Theory of Computing, 1-7, 1990.
  2. ^ A. Andersson, P. B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science, 215:337-344, 1999.
  3. ^ R. Raman. Priority queues: Small, monotone, and trans-dichotomous. Algorithms - ESA ’96, 121-137, 1996.
  4. ^ A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. Journal of the ACM, 54:3:13, 2007.