融合树——Fusion Tree

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，特性：

叉数 $B=O(w^{1/5})$
在一次搜索时，每个在搜索路径上的节点的正确的儿子可以被 $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

，那么我们可以通过：

唯一的一个区间 $[c_{j-1},c_j]$ 满足 $p$ 属于这个区间
$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

的定义，设我们需要从

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}

，使得：

$c_1+m_1<c_2+m_2<...<c_r+m_r$
对任意 $1 \le i,j \le r$ ， $c_i+m_j$ 都是两两不同的。
变换后的区间 $[c_1+m_1,c_r+m_r]$ "相对较小"，这里的相对较小其实只要是 $O( poly(r) )$ 的即可，因为这样我们可以通过调整树的叉数来满足后续的条件。

引理2：

给一个

r

个整数的序列，

c_1<...<c_r

，存在一个

r

个整数的序列，

m_1,...m_r

，满足：

$c_1+m_1<c_2+m_2<...<c_r+m_r$
对任意 $1 \le i,j \le r$ ， $c_i+m_j$ 都是两两不同的。
$(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 )

空间的。

下面给出对

$rank(K(S),u'(S))$
$rank(B(S),m)$ ，其中 $m$ 是在 $[0,w]$ 中的整数
两个 $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.一些拓展

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

放松线性空间的限制
保留线性空间的限制，但是使用随机化和整数除法

那么我们可以得到一个

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 )

的，但整数排序其实是非常复杂的一个问题，还有待研究。

融合树——Fusion Tree

文章操作

1.前言：

2.一些记号：

3.概述：

4.压缩key的表示：

引理1：

引理2：

5.融合：

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

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

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

6.一些拓展

7.总结

相关推荐

评论

融合树——Fusion Tree

文章操作

1.前言：

2.一些记号：

3.概述：

4.压缩key的表示：

引理1：

引理2：

5.融合：

O(1)O(1)O(1)计算rank(K(S),u′(S))rank(K(S),u'(S))rank(K(S),u′(S))：

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

O(1)O(1)O(1)计算msb(u,v)msb(u,v)msb(u,v)：

6.一些拓展

7.总结

相关推荐

评论

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

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

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