快速沃尔什变换($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

喵(ฅ>ω<*ฅ)

1 条评论

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

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

发表评论

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

你是机器人吗? =。= *