algorithm - 在位串中找到“适合”位模式的更好算法

我面临以下问题：给定一个相对较短的位模式，我想在一个相当长的位字符串中找到它“适合”的位置。拟合我的意思是，对于按模式设置的每一位，目标位字符串的相应位置都有一个零。

例如， , 的模式101101可以安装在以下字符串中：

等等。

“适合”的质量无关紧要，第一个按位顺序排列的好应该可以。

显然，一个简单的算法会起作用——通过对目标位串中的每个 0 进行迭代，我可以检查一个模式是否适合从该位置开始（调整模式中设置的前导位）。

然而，正如我们所知，更专业的搜索算法比简单的实现实现了巨大的加速。显然，“精确位模式搜索”算法不适用于这个问题，但考虑到收益，精确模式搜索算法提供的幼稚实现，我正在寻找是否有人已经投入了一些好的工作来设计更好的算法对于所描述的模式拟合问题。

标签： algorithmbit-manipulation

假设您检查匹配的比特流的最低位，您已将它们的副本放入lowbits.

首先执行位异或操作：

lowbits = lowbits ^ pattern;

这样，应该为零的位都变为1，我们不关心的位不变。

然后执行位与运算：

lowbits = lowbits & pattern;

不计数的位（模式为 0）被清除。

当且仅当：

lowbits == pattern

如果没有匹配，只需将比特流向右移动并继续。

如果模式适合硬件寄存器，这将变得非常有效。否则，必须将模式分解为硬件寄存器大小的块，并在每个块上重复操作，直到失败。

可能有加速比特流移位的策略（例如，对于大小为 p 的模式分为大小为 r 的寄存器的 n 块，那么您可以在每n*r-p+1一步从流中获取新位，您可以改为移位模式在函数开始时留下n*r-p+1一次，并将这些n*r-p+1情况保存在内存中）。