Фузионо стабло

Фузионо стабло представља стабло које имплементира асоцијативни низ над w-битним целим бројевима. Користи О(н) простора и извршава претрагу у О(лог^w н)) времену, које је асимптотски брже од традиционалног бинарног стабла, и у ствари боље од ван Емде Боас стабле где је w веће. То постиже брзину експлоатације појединих операција које имају константно време које је потребно у машинском језику. Фузионо стабло су осмислили Мицхаел Фредман анд Дан Wиллард.^[1]

Неколико напредних ствари је урађено од кад су Фредман и Вилард осмислили алгоритам 1990. 1999.^[2] приказано је како се може имплементирати фузионо стабло преко АЦ⁰ модела, у чијој имплементацији више није потребно константно време. Динамичка верзија фузионог стабла која користи хеш табеле је предложена 1996^[3] која је О(лог_w н) сложености. Друга динамичка верзија која је предложена 2007.^[4] користи експоненцијално стабло чија је сложеност у најгорем случају О(лог_w н + лог лог у) по операцији, где је у величина највећег кључа. Остаје отворено питање да ли ће динамичка фузија моћи да постигне сложеност од О(лог_wн) по операцији.

Како ради уреди

Фузионо стабло је у основи Б-стабло са издвајањем фактора w^1/5 (било који мали експонент долзи у обзир), који даје сложеност О(лог_w н). Да бисмо постигли жељењу радну верзију за исправке и упите, фузионим стаблом морамо омогућити да претразивање чвора подразумева више од w^1/5 кључева у константном времену. Ово се може урадити “сабијањем” кључева тако да се сви могу снаћи на машинском језику, што заузврат омогућава да се сабијање ради паралелно. Остатак овог чланка ће описати операције у статичком Фузионом стаблу, у ком су подржани само упити.

Скицирање уреди

Скицирање је метод који подразумева да сваки w-битни кључ у чвору садржи к кључева који су компресовани на само к-1 бита. Сваки кључ x може се посматрати као део бинарног стабла висине w који почиње кореном и завршава се листом који одговара x. Да би се разликовала два дела, довољно је погледати у њихове тачке гранања (први бит где се два кључа разликују). Сви к делови заједно имају к-1 тачки гранања, зато је потребно највише к-1 бита да би се разликовали било који од к кључева.

Важна улога скицирања је да чува ред кључева. То је, скетцх(x) < скетцх(y) за било која сва кључа где је x<y.

Приближна скица уреди

Ако је запис компресованих бита б₁ < б₂ < ··· < б_р, онда је компресовање кључа x_w-1···x₁x₀ р-битног целог броја $x_{b_{r}}x_{b_{r-1}}\cdots x_{b_{1}}$ . Са стандардним операцијама какве се користе у C језику, тешко је директно израчунати компресовање кључа у константном времену. Умсето тога, компресовани битови могу бити запаковани у опсегу величине од највише р⁴ , користећи битовско АНД и множење. Битовско АНД служи да уклони све некомпресоване битове из кључа, док множење помера компресоване битове у мали низ. Као и „савршена“ скица, скица чува приближан распоред кључева. За неке речи је потребно утврдити тачан број умножавања константи. Сваки компресовани бит на локацији б_и ће множењем бити померен на б_и + м_и преко м = $\textstyle \sum _{i=1}^{r}$ . За приближно скицирање морамо се држати следећих правила:

б_и + м_ј су различити за сваки пар (и, ј). То нам гарантује да компресовани битови неће бити оштећени приликом множења.
б_и + м_ј је строго растућа функција од и. То значи да је редослед компресованих битова очуван.
(б_р + м_р) - (б₁ - м₁) ≤ р⁴. То значи да су компресовани битови запаковани у опсегу величине од р⁴.

Индуктивни аргумент показује како ми може бити конструисан. Нека је м₁ = w − б₁. Претпоставимо да 1 < т ≤ р и да су 'м₁, м₂... м_т већ изабрани. Онда се изабере најмањи цео број м_т који задовољава особине (1) и (2). Особина (1) захтева да м_т ≠ б_и − б_ј + м_л за све 1 ≤ и, ј ≤ р и 1 ≤ л ≤ т-1. Према томе, постоји мање од тр² ≤ р³ који м_т мора да задовољава. Кад је м_т изабран да буде минимум,(б_т + м_т) ≤ (б_т-1 + м_т-1) + р³. Ово објашњава особину (3).

Приближан запис се израчунава на следећи начин: 1. Маскирају се сви компресовани и битови који су коњуговани . 2. Множењем кључ ће бити предодређен за константу м. Ова операција у ствари захтева две машинске речи , али ово и даље може бити урађено у константном времену. 3. Маскира се све, осим померених компресованих битова. Они се сада смештају у суседни блок од највише р⁴ < w^4/5 бита. У наставку овог чланка, компресовање ће означавати приближно скицирање.

Паралелно поређење уреди

Циљ компресије је да сабијањем дозволи да сви кључеви буду смештени у једну w-битну реч. Онда ће сабијање чвора бити следећи низ знакова: 1sketch(x₁)1sketch(x₂)...1sketch(x_к) . Можемо видети да скетцх функција користи тачно б ≤ р⁴ бита. Затим, сваки блок користи 1 + б ≤ w^4/5 бита, а од к ≤ w^1/5 , укупан број битова у чвору је највише w. Укратко: за низ с и не негативни број м, с^м означава уланчавање низа с м пута. Ако је т такође низ, ст означава низ од т до с. Скицирање чвора омогућава нам да претразујемо кључ за било који б-битни цео број y. Нека је з = (0y)^к може бити израчунато и у константном времену (множење у константом (0^б1)^к). Напоменимо да је 1sketch(x_и) - 0y увек позитивно, али чува водећу скицу 1 ифф sketch(x_и) ≥ y. Ми на тај начин можемо израчунати најмањи индеx и тако да sketch(x_и) ≥ y подразумева

Одузимањем з из чвора
Узети разлике битовског „И“ и константе (10^б)^к. Ово брише све осим водећег бита сваког блока.
Наћи најважнији бит резултата.
Израчунати и, користећи чињеницу да је водећи бит и-тог блока имаминдеx и(б+1).

Декомпресовање уреди

За произвољан упит, паралелна компарација израчунава индекс и према следећој формули

sketch(x_и-1) ≤ sketch(q) ≤ sketch(x_и).

Нажалост, шема функције не чува копију кључева тако да није неопходно да x_и-1 ≤ q ≤ x_и. Шта је тачно у томе, од свих кључева, било x_и-1 ор x_и имају најдужи заједнички префикс са q. То је зато што било који кључ y са дужим префиском истим са q, такође има више заједничких компресованих битова са q, и sketch(q) је много сличнији sketch(x_ј). Најдужи заједнички префикс између два w-битна цела броја а и б могу бити израчунати у константном времену, тако што се тражи најзначајнији бит дискјункције од а и б. Ово се може употребити као маска за све бите сем за заједничке префиксне битове. Напоменимо да п тачно дефинише где се q гранање завршава.Ако је следећи бит од q 0, онда се наследник од q налази у п₁ подстаблу, и ако је следећи бит од q 1, онда се предак од q налази у п₀ подстаблу. Ово прати следећи алгоритам:

Користи се паралелна компарација да се нађе следећи индекс и тако да важи скетцхsketch(x_и-1) ≤ sketch(q) ≤ sketch(x_и).
Израчунава се најдузи заједнички префикс од п и q, било x_и-1 или x_и (узима се дужи од ова два).
Нека је л-1 дужина најдужег заједничког префикса са п.
1. Ако је л-ти бит од q једнак 0, онда је е = п10^w-л. Користити паралелну комапарацију да се нађе наследник од скетцх(е). То је у ствари предак од q.
2. Ко је л-ти бит од q једнак 1, онда е = п01^w-л.Користи се компарација да се нађе предак од sketch(е). То је у ствари наследник од q.
Када једном нађемо претка или наследника од q, тачна позиција q у групи кључева је одређена.

Референце уреди

^ M. L. Фредман анд D. Е. Wиллард. БЛАСТИНГ тхроугх тхе информатион тхеоретиц барриер wитх ФУСИОН ТРЕЕС. Процеедингс оф тхе тwентy-сецонд аннуал АЦМ сyмпосиум он Тхеорy оф Цомпутинг, 1-7, 1990.
^ А. Андерссон, П. Б. Милтерсен, анд M. Тхоруп. Фусион треес цан бе имплементед wитх АЦ0 инструцтионс онлy. Тхеоретицал Цомпутер Сциенце, 215:337-344, 1999.
^ Р. Раман. Приоритy qуеуес: Смалл, монотоне, анд транс-дицхотомоус. Алгоритхмс - ЕСА ’96, 121-137, 1996.
^ А. Андерссон анд M. Тхоруп. Дyнамиц ордеред сетс wитх еxпонентиал сеарцх треес. Јоурнал оф тхе АЦМ, 54:3:13, 2007.

МИТ ЦС 6.897: Адванцед Дата Струцтурес: Лецтуре 4, Фусион Треес, Проф. Ерик Демаине (Спринг 2003)
МИТ ЦС 6.897: Адванцед Дата Струцтурес: Лецтуре 5, Море фусион треес; селф-организинг дата струцтурес, мове-то-фронт, статиц оптималитy, Проф. Ерик Демаине (Спринг 2003)
МИТ ЦС 6.851: Адванцед Дата Струцтурес: Лецтуре 13, Фусион Трее нотес, Проф. Ерик Демаине (Спринг 2007)
МИТ ЦС 6.851: Адванцед Дата Струцтурес: Лецтуре 12, Фусион Трее нотес, Проф. Ерик Демаине (Спринг 2012)

[1] M. L. Фредман анд D. Е. Wиллард. БЛАСТИНГ тхроугх тхе информатион тхеоретиц барриер wитх ФУСИОН ТРЕЕС. Процеедингс оф тхе тwентy-сецонд аннуал АЦМ сyмпосиум он Тхеорy оф Цомпутинг, 1-7, 1990.

[2] А. Андерссон, П. Б. Милтерсен, анд M. Тхоруп. Фусион треес цан бе имплементед wитх АЦ0 инструцтионс онлy. Тхеоретицал Цомпутер Сциенце, 215:337-344, 1999.

[3] Р. Раман. Приоритy qуеуес: Смалл, монотоне, анд транс-дицхотомоус. Алгоритхмс - ЕСА ’96, 121-137, 1996.

[4] А. Андерссон анд M. Тхоруп. Дyнамиц ордеред сетс wитх еxпонентиал сеарцх треес. Јоурнал оф тхе АЦМ, 54:3:13, 2007.

[1]

[2]

[3]

[4]