快速沃尔什变换

Published: by Creative Commons Licence

  • Tags:

引言

快速沃尔什变换(Fast Walsh Transform)适用于计算一类多项式卷积的高效算法。定义

其中$A$,$B$,$C$均为$n$阶多项式。而$A_i$,$B_j$分别表示多项式$A$中$X^i$项的系数和多项式$B$中$X^j$项的系数。

看着眼熟吧,这不是和多项式的乘法非常像吗,当$i\oplus j=i+j$时,上面就是我们熟知的多项式乘法公式。我们知道解决多项式乘法不仅有$O(n^2)$的朴素算法,还有$O(n\log_2n)$的快速傅里叶变换。快速傅里叶变换实际上是将两个多项式$A$,$B$转换为点值表示法DFT(A)和DFT(B),之后利用向量乘法得到DFT(C)=DFT(A)DFT(B),最后从DFT(C)中还原多项式$C$。我们不免想到,是否能利用同样的技术进行加速呢?

或运算

如果$i\oplus j=i\mid j$,那么我们可以定义:

其中$j\in i$表示j中$1$出现的二进制位置是$i$的子集,换言之$i=i\mid j$。我们注意到

因此我们发现了$FWT(C)=FWT(A)\cdot FWT(B)$。下面我们讨论如何快速计算$FWT(A)$。记$m=\lceil \frac{n}{2} \rceil$,$L(A)=\sum_{i=0}^{m-1}A_iX^i$,$R(A)=\sum_{i=m}^nA_iX^i$。很显然$A=L(A)+R(A)\cdot X^m$。

我们可以简单地记作

这样我们可以每次都将$A$拆分为前部和后部进行分治计算。时间复杂度为$O(n\log_2n)$。而$FWT$的逆也很容易得到:

同样可以采用分治算法解决。

且运算

如果$\oplus$代表且运算,那么$FWT$函数定义如下:

其余推理类似,不再赘述,直接给出公式:

异或运算

如果$\oplus$代表亦或运算。记$E$为所有二进制形式中1的个数为偶数个的正整数集合,而$O$表示所有二进制形式中1的个数为奇数个的正整数集合。那么$FWT$函数定义如下:

由于(可以通过枚举证明)

因此:

记$b(i)$表示$i$的二进制形式中$1$的个数。记$r$表示$i\oplus j$中可能的$1$的数量,初始值为$b(i)+b(j)$。遍历每一位,若浏览某一位时,$i$与$j$均为$0$,则$r$不变,若一者为$1$,$r$依旧不变,否则二者都为$1$,则$r$减少2。很显然这个算法最终得到的就是$b(i\&j)$。因此我们证明了$b(i\&j)$与$b(i)+b(j)$的二进制形式中1出现的次数拥有相同的奇偶性。

因此我们可以推出:

接着我们考虑如何拆分多项式。

而逆函数容易得到:

整体的时间复杂度为$O(n\log_2n)$。