快速沃尔什变换(FWT)

快速沃尔什变换(Fast Walsh-Hadamard Transform,FWT)是一种用于高效计算位运算卷积的算法。它与快速傅里叶变换在思想上高度类似:先将序列变换到某个域,在该域中卷积退化为逐点相乘,最后再逆变换回来,从而把原本平方级的卷积加速到线性对数级。

概述

普通卷积中,结果下标是两输入下标之和;而位运算卷积中,结果下标由两输入下标做按位与、按位或或按位异或得到。FWT 针对这三种位运算分别设计了对应的正交变换,使得变换后逐点乘积再逆变换即可得到卷积结果。异或卷积对应的变换恰为沃尔什-阿达玛变换,因此得名。

核心原理

• 整体流程为:对两个长度为 2 的幂的数组各做一次 FWT,把对应位置相乘,再对结果做一次逆 FWT。
• 异或卷积:采用蝶形结构,每层将下标某一位为零和为一的两项做加减组合,逆变换时除以二。
• 按位或卷积:相当于对每一位做子集和变换,把包含某子集的项累加。
• 按位与卷积:类似或卷积,但按超集方向累加。
• 由于变换在每一位上独立进行,共 log 层,每层线性,总复杂度为 O(n log n)。

应用场景

FWT 广泛用于需要计算子集或位运算卷积的问题,例如集合幂级数、状态压缩动态规划中的合并、异或最值统计以及某些组合计数问题。它是子集和变换、集合幂级数运算的基础,也常与生成函数结合使用。

常见问题

问:FWT 和 FFT 有什么本质联系?答:两者都遵循变换、逐点乘、逆变换的框架,区别在于卷积定义的运算不同,FFT 处理下标相加,FWT 处理下标的位运算,因而所用的正交基不同。

问:为什么数组长度要是 2 的幂?答:位运算作用在二进制位上,长度取 2 的幂才能覆盖固定位数的所有取值,并让蝶形分治按位递归的结构成立。