快速沃尔什变换 ($Fast Walsh-Hadamard Transform$, 简称 $FWT$),是一种可以加速集合卷积的算法

会 $FFT$的同学肯定知道,$FFT$加速多项式乘法实际上就是加速了一个卷积。在 $FFT$里,卷积的形式是长这个样子的:

$$C(k)=\sum_{i+j=k}A(i)B(j)$$

而所谓集合卷积又是一个怎样的东西呢?其实它就是长这个样子的

$$C(k)=\sum_{i\times j=k}A(i)B(j)$$

其中 $\times$指的是一个集合运算符

那 $FWT$这东西具体是怎么操作的呢?

让我们来首先回忆一下 $FFT$是怎样操作的:
1. 利用 $dft$将多项式变为点值表示(运用分治思想)
2. 将点值相乘
3. 利用 $idft$将点值变回原来的系数形式

现在我来说一下 $FWT$的思路,其实和 $FFT$是十分相似的:
1. 利用 $FWT$变换将原数组变为点值表示(也要分治)
2. 将点值相乘
3. 利用 $UFWT$变换将点值变回来

这样说似乎有点抽象,总结来说就是将原来的卷积运算变为点值运算,这里我们定义 $\;\cdot\;$为点乘运算符,效果是将两个数组对应位相乘,复杂度是 $\Theta(n)$的,因此我们要寻找一组变换及其逆运算 $FWT()$和 $UFWT()$,使得它满足 $FWT(A) \cdot FWT(B) = FWT(C)$且 $A’=FWT(A)\quad A=UFWT(A’)$

而我们现在的核心问题就是找到这个运算,比较 $exciting$的是,对于每种运算,它的 $FWT$变换往往都有一定的差别(但差别不是特别大)我们先从或运算 $’|’$开始了解这个神秘的变换

首先或运算的 $FWT$是长这样的:
$$A'[i]=\sum_{i|j=i}A[j]$$

我们该如何理解这个式子呢?其实我们可以把 $i,j$都看作一个集合(由二进制数表示),接着我们会发现上面运算的实质就是将 i 中的所有子集求和,我们会发现通过这种变换后 $A’\cdot B’=C’$这个式子是成立的,这里给出证明:

设 $i$为定义域内任意数,则上式变为
$$A'[i] \cdot B'[i]=C'[i]$$
接着将式子展开:
$$(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|j=i}C[j]$$
再将右边展开:
$$(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|j=i}\sum_{k_1|k_2=j}A[k_1]B[k_2]$$

考虑换元,即:
$$
\begin{array}{c}
i|j&=i\\
i|k_1|k_2 &= i
\end{array}
$$
即 $k_1$和 $k_2$也是 $i$的子集,于是原式化为:
$$
(\sum_{i|j=i}A[j])\cdot(\sum_{i|j=i}B[j])=\sum_{i|k_1=i}\sum_{i|k_2=j}A[k_1]B[k_2]
$$
易知左右两边是相等的

嗯那我们既然已经证明了这个,那现在的问题是如何由 $A$快速通过 $FWT$求得 $A’$

我会枚举子集

那你这个时间复杂度就退化成原来的啦!

考虑类似 $FFT$里面的分治思想。

为了方便分治,我们假设 $A’$数组的长度是 $2^k$的(不足的位数在前面补上 $0$,和 $FFT$差不多的),接着我们将 $A’$分为两半,设 $A’=\{a_1,a_2,\cdots,a_{2^k}\}$,那么 $A_1’=\{a_{2^{k-1}+1}, a_{2^{k-1}+2},\cdots,a_{2^k}\}$,$A_0’=\{a_1, a_2,\cdots,a_{2^{k-1}}\}$

假设我们已经知道了 $A_0′,A_1’$,我们如何求 $A’$呢?

考虑我们当前求的 $A’$的下标是 $k$,则 $A_0′,A_1’$的唯一的不同就在当前最高位,$A_0’$这一位是 $0$,$A_1’$这一位是 $1$,我们可以发现,如果这一位是 $0$的话,根据或的性质,只有 $A_0’$是它的子集(最高位只能填 $0$呀),如果这一位是 $1$的话,那么 $A_1′,A_0’$都是它的子集(最高位随便填呀),因此我们便得到一个这样的函数:
$$A’=merge(A_0′,A_0’+A_1′)$$
其中 $merge(x,y)$能将 $x,y$两个数组拼起来,$+$指的就是按数组下标相加喽。

因此我们就能够用 $\Theta(nlogn)$的复杂度求出 $A’$了

那逆变换怎么搞呢?

其实我们可以根据刚才推出来的东西倒着推回去,我们知道:
$$A_0’=A_0,A_1’=A_0+A_1$$
那么很容易可以推出:
$$A_0=A_0′,A_1=A_1′-A_0’$$

接着用类似上面的方法就能推回去啦~

(感觉自己还是讲的好玄乎呀 QAQ)

对于与运算,异或运算,我们也可以用类似的方法推一遍,这里给出它们最后的公式:

与运算:
$$A’=merge(A_0’+A_1′,A_1′)$$
$$A=merge(A_0-A_1,A_1)$$

异或运算:
$$A’=merge(A_0’+A_1′,A_0′-A_1′)$$
$$A=merge(\frac{A_0+A_1}2,\frac{A_0-A_1}2)$$

与运算跟或运算的推导过程差不多,异或运算的推导我还有点昏(捂脸)

QAQ 蒟蒻的我也只能记一下公式了。

分类: 文章

quhengyi11

AFO 有缘再见

1 条评论

konnyakuxzy · 2018年4月19日 12:27 下午

Orz 最近没有时间看
等后面脱离常规的时候再看吧 QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注