融合树——Fusion Tree

2019-10-25 00:29:48


1.前言:

Fusion Tree,中文译作融合树,是一种亚log的数据结构,与1993年由Michael L.Fredman和Dan E.Willard提出。

用途:$O( \log n/ \log w+ \log w )$时间复杂度支持插入,删除,前驱,后继,min,max,以及用于整数排序。

信息论断言对$n$个数的排序在最坏情况下需要$n\log n$次比较,不过对这个界我们还需要一些研究。

有人证明了任意unit cost RAM算法,其中只包含加法,减法,乘法,和0比较(但是不包含除法和位运算)最坏情况下需要$\Omega(n\log n)$的时间去对$n$个数排序。

如果允许使用除法和位运算,他们有一个线性时间复杂度的算法,但是这个算法对unit cost滥用。

这里我们规定我们使用的计算模型的字长是w,每个输入的数都是在$[0,2^w-1]$中的整数。

2.一些记号:

对于一个集合$S$和一个整数$x$,定义$rank(S,x)$为S集合中$\le x$的元素个数。 对于一些非负整数$a$,定义$bin(a_1,...,a_n)=2^{a_i}+...+2^{a_n}$。

对于两个非负整数$a,b$,定义$msb(u,v)$为$u$和$v$最高的不相同的位。

3.概述:

Fusion Tree大概可以看做是一棵特殊的B-Tree,特性:

  1. 叉数$B=O(w^{1/5})$

  2. 在一次搜索时,每个在搜索路径上的节点的正确的儿子可以被$O(1)$确定

从这些特性我们可以看出Fusion Tree单次操作的时间复杂度是$O( \log _w(n) + \log w) = O( \log n/\log w +\log w)$的,比$O( \log n )$低。

但是由于其实现方式,Fusion Tree每次对内部节点的更新复杂度是$O( B^4 )$的。 为了控制Fusion Tree均摊的更新复杂度,我们将这棵B-Tree的每对叶子节点之间的部分替换为一个大小大约为$O( B^4 )$的Weight Balanced Tree,只在WBT根节点发生变化的时候更新Fusion Tree的内部节点。

具体来说,我们B-Tree维护的是一个排序后的数组的分块,其中每个块都由一棵平衡二叉搜索树维护,fusion tree上只维护一个值来表示块边界,用途是指引每次插入,删除,查询在哪个块中。

可以发现这样我们把内部节点的变化次数除掉了一个$B^4$。

4.压缩key的表示:

如何$O(1)$确定搜索路径上的一个节点的正确的儿子:

考虑一个B-Tree的节点,其上面包含了$k$个key,其中$B/2 \le k \le B$,记作$S={u_1,u_2,...u_k}$。

然后我们定义出$B(S)$表示"有区别的位的位置",用人话来说就是我们把这$k$个key的trie建出来,然后所有有超过$1$个儿子的节点的高度构成的集合 (当然这里我们不用把trie建出来,只是这么解释比较直观,而且更能反映出其的一些性质)。

再定义一个集合$K(S)$,为$S$只保留$B(S)$中那些位之后的值,记作$K(S)={u'_1,u'_2,...u'_k}$,发现这个压缩操作对于原集合是保序的。

对于一个任意的$w-bit$的数$u$,我们记$u'(S)$表示$u$只保留$B(S)$中那些位,即把非$B(S)$中的位都置为$0$之后的值。

下面引理表达了一个压缩key的重要性质:

引理1:

设$B(S)$排序后为$c_1<c_2<...<c_r$,定义边界$c_0=-1,c_{r+1}=b$。

定义$u'_i$为$K(S)$中任意的一个压缩后的key。

对于一个任意的$w-bit$的数$u$,满足$u \neq u_i$,

设$msb(u'(S),u'_i)=c_m$,即$u$和$u_i$在bit位置$c_{m+1},...,c_r$位置处相等,但是在$c_m$处不相等,如果$u'(S)=u'_i$,则我们记$m=0$。

如果$u$和$u_i$不同的最高位$p$满足$p>c_m$,那么我们可以通过:

  1. 唯一的一个区间$[c_{j-1},c_j]$满足$p$属于这个区间

  2. $u$和$u_i$的大小关系

来确定$rank(S,u)$的值。

证明平凡,把trie画出来,显然可以画成一个平面图,然后可以发现这两个可以唯一地确定出一个平面区域,这个区域中的$S$集合元素个数就是$rank(S,u)$(感觉这种东西光写一堆自然语言也不能说明正确性,需要形式化证明一下?)。

注意到这个引理虽然是对任意$u_i$成立的,但是要求$u$和$u_i$不相同的最高位不是$B(S)$中的一个点,可以发现这个$u_i$其实必须在$u$"脱离"这个trie的位置,也就是$p$的父亲子树中。

引理$1$使得我们可以将$rank(S,u)$的计算规模降低到$rank(K(S),u'(S))$,通过计算$rank(K(S),u'(S))$,我们可以确定$u'(S)$在$K(S)$中的前驱后继$u'_j$和$u'_{j+1}$(这两个值不一定存在,但经过平凡的讨论就可以解决。

如果$u_j \le u \le u_{j+1}$,那我们已经解决了这个问题 否则我们令$i=j$或者$i=j+1$,计算出$msb(u_i,u)=p$,然后只要我们知道了包含$p$的区间$[c_j,c_{j+1}]$,我们就可以通过引理$1$来确定出$rank(S,u)$的值。

这里如果我们$u_j \le u \le u_{j+1}$,那我们已经达成了目的,不用继续考虑了。

否则如果不满足$u_j \le u \le u_{j+1}$,也就是说我们在这个sketch的过程中丢失了信息,即说明保留$K(S)$这些位的信息是不够的,那么$p$一定不在$K(S)$中,也就是说$i=j$和$i=j+1$中$p$较小的$i$满足$p>c_m$,故可以使用引理$1$。

计算$K(S)$和$u'(S)$: 我们发现没有平凡的方法可以将一个$w-bit$的数$u$在$O(1)$时间把$B(S)$那些位提取出来之后放到连续的一段中(可能可以通过硬件支持实现?),即使经过了一定预处理。

其实我们不需要做到这个,可以用具有:

  1. 将需要提取出的位提取出,并放到(可以不连续)的更短的一段中

  2. 保序性

的其他变化来实现我们需要的效果。

我们可以通过一次恰当的乘法和一次与运算来实现这个:

沿用引理$1$的定义,设我们需要从$u$中提取这些位,令$C=bin(c_1,...,c_r)$。

假设我们已经算出了$C$,我们先通过令$v=u\;\mathrm{AND}\;C$来将$u$中不需要的那些位置$0$。

然后我们将$v$乘以一个量$M$,从而把$v$中我们需要的那些$bit$转化到一个狭窄的范围内,然后再通过一次$\mathrm{AND}$来清除掉不需要的位置 这里给出对一个量$M$的存在性证明和构造:

记$M=bin(m_1,...,m_r)$,如果我们暂时忽略交叉和进位造成的影响,那么可以认为$v$乘$M$是把$c_1,...c_r$这些位置的位重新定位到了。

$c_1+m_1,...,c_r+m_r$上。

如果对任意$1 \le i,j \le r$,这$r^2$个$c_i+m_j$都是不同的,那么就不会发生交叉和进位了。

我们现在的目标是构造一个整数集合${m_1,...,m_r}$,使得:

  1. $c_1+m_1<c_2+m_2<...<c_r+m_r$

  2. 对任意$1 \le i,j \le r$,$c_i+m_j$都是两两不同的。

  3. 变换后的区间$[c_1+m_1,c_r+m_r]$"相对较小",这里的相对较小其实只要是$O( poly(r) )$的即可,因为这样我们可以通过调整树的叉数来满足后续的条件。

引理2:

给一个$r$个整数的序列,$c_1<...<c_r$,存在一个$r$个整数的序列,$m_1,...m_r$,满足:

  1. $c_1+m_1<c_2+m_2<...<c_r+m_r$

  2. 对任意$1 \le i,j \le r$,$c_i+m_j$都是两两不同的。

  3. $(c_r+m_r)-(c_1+m_1) \le r^4$

证明:

先考虑证明存在整数序列$m'_1,...,m'_r$,使得对任意$i,j,a,b$,$m'_i+c_a$与$m'_j+c_b$在模$r^3$的意义下不同余。

如果我们找到了这样的整数序列,那么所有$r^2$个$c_i+m'_j$都是两两不同的,并且由于这个是在模$r^3$意义下两两不同的,所以我们可以对第$i$个$c_i+m'_i$加上$(i-1)*r^3$,这样就可以保证对所有$i$满足$c_i+m'_i<c_{i+1}+m'_{i+1}$了。

关于$m'_1,...,m'_r$的存在性:

使用数学归纳法来证明,显然我们可以找到$m'_1$,这个平凡。

假设结论对$t$成立,即我们已经找到了$m'_1,...,m'_t$,满足对任意$1 \le i,j \le t$,$a,b$,有$m'_i+c_a$与$m'_j+c_b$在模$r^3$的意义下不同余。 可以观察到$m'_{t+1}+c_i \equiv m'_s+c_j (\mod r^3\;)$,即$m'_{t+1} \equiv m'_s+c_j-c_i (\mod r^3\;)$。

我们可以令$m'_{t+1}$是$[0,r^3)$中最小的和所有$m'_s+c_j-c_i$不同余的数,这里$1 \le s \le t,1 \le i,j \le r$。

由鸽巢原理,由于$t*r^2<r^3$,所以我们一定可以找到$m'_{t+1}$。

故当$t+1 \le s$时,结论对$t+1$成立 由数学归纳法知结论对$s$成立,同时我们这里给出了一个暴力的$O( r^4 )$的构造算法($r$轮,每轮最坏枚举$O( r^3 )$个位置)。

5.融合:

融合树的"融合"即指将每个节点上的key放到同一个$w-bit$的word上,通过对这个word进行运算来一起处理这些key。

沿用之前$u_i$和$B(S)=\{c_i\}$的记号:

我们这个B-Tree的每个节点存了$C=bin(c_1,...c_r)$和$M=bin(m_1,...,m_r)$这两个量,用于计算$u'(S)$,同时还存了$D=bin(c_1+m_1,...,c_r+m_r)$这个量,用于清空$u'(S)$的计算中不需要的位。

同时还需要两个数组,存排序后的$u_i$和$u'_i$,和一个表$f[i][j][2]$表示引理$1$中,如果知道了$u_i$和$j$,还有$u$和$u_i$的大小关系,我们唯一确定的答案是多少。

回顾之前的内容,当我们算出了$j=rank(K(S),u'(S))$后,如果$u$不在$[u_j,u_{j+1}]$的区间中,那么我们把$u'(S) \;\mathrm{XOR}\; u'_j$和$u'(S) \;\mathrm{XOR}\; u'_{j+1}$比较一下,较小的值所对应的$u'_h$,$h=j$或$j+1$,和$u$有更长的公共前缀,即$msb$更小。

令$m=msb(u,u_h)$,然后我们需要知道$m$被哪个$B(S)$中的区间$[c_i,c_{i+1}]$包含,所以需要进行一次$i=rank(B(S),m)$的计算 还需要进行一次$u$和$u_h$的比较,这个平凡,当这些都做完了,我们查一下表$f$即可得到$rank(S,u)$。

可以发现fusion tree的每个内部节点需要存下$O( B^2 )$大小的表,内部节点个数是$O( n/B^4 )$个,所以是$O( n )$空间的。

下面给出对

  1. $rank(K(S),u'(S))$

  2. $rank(B(S),m)$,其中$m$是在$[0,w]$中的整数

  3. 两个$w-bit$的整数$u,v$,$msb(u,v)$

的计算方法:

$O(1)$计算$rank(K(S),u'(S))$:

我们把每个$K(S)$中的元素前面补一个$1$,然后从小到大拼到一起来,这个拼起来的操作就是所谓的"融合"。

由于我们$K(S)$中有$k$个元素,每个元素有$r^4$位,所以这里总共用了$k(r^4+1)$位,由于$B/2 \le k \le B$,所以我们总的位数是$O( B^5 )$的,由于$B=O( w^{1/5} )$,所以总的位数是$O( w )$的。

所以我们拼起来的这个东西是$O( 1 )$个word的,这里将其定义为$A$。

令$C=\sum \limits _{i = 0} ^ {B} 2^{(r^4+1)i}$ 通过$u'(S) \times C$,可以将$u'(S)$前面补一个$0$之后复制$B$遍,然后拼到一起 通过$A-u'(S) \times C$,可以发现对每个$A$中补$1$的位置,其对应的那个$u_i(S)$如果$<u'(S)$,则这个$1$变成$0$,否则$1$不变 所以我们通过$(A-u'(S) \times C)\&C$,然后对这个word数$1$的个数即可知道$rank(K(S),u'(S))$。

由于这个word只在$2^{(r^4+1)i}$这样的位置有$1$,我们可以通过一次对$2^{r^4+1}-1$的取模来得到其中$1$的个数,虽然对常数取模可以用乘法和位运算$O(1)$实现,但我们这里可以给出一个更合适的构造。

我们可以通过将其乘$C \& (2^{(r^4+1)k}-1)$,这样相当于把其叠加了$k$次之后加起来,可以发现其中有一个长为$r^4+1$的段,这段的二进制表示的值等于这个word在$2^{(r^4+1)i}$这些位置的元素的和。

通过位移和$\mathrm{AND}$我们可以取出这个长$r^4+1$的段,于是就完成了。

答案即$((((A-u'(S) \times C) \& C) \times (C \& (2^{(r^4+1)k}-1))) \& C)>>((k(r^4+1)-1)$

$O(1)$计算$rank(B(S),m)$,$m$是在$[0,w]$中的整数:

由于我们可以$O(1)$计算$rank(K(S),u'(S))$,所以把这个查出来然后判断那一个数的大小,并且进行一次查表即可。

$O(1)$计算$msb(u,v)$:

等价于求$u \;\mathrm{XOR}\; v$的最高位$1$的位置,设$A=u \;\mathrm{XOR}\; v$。

我们将$A$分为$r^c$大小的块,总共$r$块,这里$c$是一个常数,$c>1$ 令$C=(100...0100...0......)_2$,这里每两个$1$之间有$r-1$个$1$,$C$是一个常数。

注意到:

$((100...0)_2-0)\&(1<<(r^c)-1)=(1<<(r^c)-1)$

$((100...0)_2-y)\&(1<<(r^c)-1)=0$,这里$y>0$

先考虑对每个块去掉首位,块内是否有$1$。

我们用$A\& \sim C$可以去掉每一块的首位。

然后用$C-(A\& \sim C)$可以使得每一块中除首位外如果有$1$,则其在该块首位为$0$,否则为$1$。

然后用$(C-(A\& \sim C))\&C$去掉了$C-(A\& \sim C)$中每一块中除首位外的部分。

然后用$(C-((C-(A\& \sim C))\&C))$可以得到:如果一块中除首位外有$1$,则块首位为$1$,否则为$0$,且块首位外所有位置都是$0$的一个数 再考虑对每个块只保留首位,块内是否有$1$。

这个用$A\&C$即可。

最后$(A\&C)|(C-((C-(A\& \sim C))\&C))$可以得到:如果一块中有$1$,则块首位为$1$,否则为$0$,且块首位外所有位置都是$0$的一个数。

令$D= \sum \limits _{k=0}^{r-1} 2^{k(r^c-1)}$,

通过$(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r)$可以将每块首位的数字拼到一个长$r$的二进制数中。

然后我们可以使用前面的$O(1)$计算$rank$的方法,令$B'(S)={2^i}$,$i$在$[0,r-1]$间,是整数。

通过$rank(B'(S),(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r))$就可以得到这个长$r$的二进制数中第一个非0的首位的位置了。

我们知道了第一个非$0$位在哪个块中,然后查这个块里面第一个非$0$位的位置就可以了。

由于我们每个块是$r^c$的大小,所以对一个大小为$r^c$,包含了$2^i$的集合用一次rank即找到了块内第一个非$0$的首位位置。

取$c=4,r=w^{1/5}$,$r^c=w^{4/5}$,我们便$O(1)$查询,$O(w^{4/5})$预处理时间复杂度解决了这个问题,由于预处理次数是$O( n/B^4 )$,所以这里也是线性的。

综上所述,我们得到了一个单次操作复杂度$O( \log n/\log w + \log w )$的数据结构,这里据说可以通过一些优化做到$O( \log n/\log w )$,但在这里由于我还没看所以暂时不做介绍。

6.一些拓展

如果我们允许下列中的一个:

  1. 放松线性空间的限制

  2. 保留线性空间的限制,但是使用随机化和整数除法

那么我们可以得到一个$O( \sqrt{ \log n } )$的动态搜索的时间复杂度上界。

当$n$超过$2^{(\log w)^2/36}$时(这里$1/36$的常数是论文中给出的,由于我的部分细节和论文中不同,可能是不同的常数),

对于1的case,可以通过使用vEB树来实现,对于2的case,可以通过使用Y-fast trie实现。

对于这样的$n$,这两个数据结构可以在$O( \log \log U )=O( \log w )=O( \sqrt{\log n} )$的时间完成一次搜索操作。

当$n$小于这个数时,

对于较小的$n$,我们使用fusion tree,通过调节$B=Θ(2^ {\sqrt{\log n}})$。

在这个$B$下,我们的时间复杂度是$O( \log n/\log B + \log B ) = O( \sqrt{\log n} )$。

综上所述,如果引入随机化和整数除法,可以$O( n \sqrt{\log n} )$时间,线性空间整数排序。

7.总结

由信息论可以证明基于比较的排序下界是$\Omega( n\log n )$的,但整数排序其实是非常复杂的一个问题,还有待研究。