问如何在长模式中模糊匹配短位模式？

EN

您要查找的运算是人口计数或密切相关的汉明距离。

与其手动实现大量的逐位运算，不如尝试一下包含several bit-string functions的Gnu Multi-Precision Library。

• 使用mpz_tdiv_q_2exp一次右移长模式一位，使用
  • 提取最后150位，使用mpz_tdiv_q_2exp查找在提取的位和短模式之间翻转的位数。

应该足够快，而且写起来也很快！

作为初始优化，我建议将150位的模式以1位的增量移动到7位，这样您就有8个模式可供匹配，从150位到157位。然后，不是一次将长模式移位一位(这很慢，并且可能主导运行时)，而是一次移位8位。请务必清除您不希望比较的位。

让我们调用短位序列S和长位序列L。我心目中的算法如下：

1- XOR S with size(S) rightmost bits of L. Say this is R
2- AND R with R-1 until zero, count how many times, if less than threshold 
   pattern is found
3- Shift right L and go to 1 if size(L) >= size(S)

在最坏的情况下，这应该会占用O(size(L)*size(S))时间。但由于在每次迭代中，1的数量远远小于size(S)，因此在实践中它应该是有效的。

沿着较长的比特模式移动的解决方案的复杂度为O (N *M) (N-短段大小，M-长段大小)。

如果大小将增长，您可以将其视为寻找两个信号之间的移位最大化(或超过阈值)相关性的问题，并使用快速傅立叶变换加快速度。如果我没记错的话，这可能会给出类似O(N*logN)的结果。