1

我在尝试匹配长位模式中的短位模式时遇到问题：我有一个长位模式，例如 6k 位，存储在 char 数组中，还有一个短位模式，比如 150 位，也存储在 char 数组中. 现在我想检查短位模式是否在长位模式中。虽然不需要短位模式精确匹配长位模式的某些部分，但我将定义一个阈值，如果低于它的误码率，我将采用两个模式匹配。

考虑到错位问题，我想不出一个优雅的解决方案。我能找到的一种方法是将位模式转换为字符模式，即将位 1 转换为“1”，将 0 转换为“0”并应用一些字符串匹配算法。但我担心它可能会使我的系统负担增加 7-8 倍的内存。我周围有人推荐Rabin Fingerprint，但它似乎不是为此类问题而设计的。

希望你能帮我一把。

谢谢和最好的问候。

4

3 回答 3

2

您正在寻找的操作是人口计数或密切相关的汉明距离。

与其手动实现大量的按位运算，不如试试Gnu Multi-Precision Library，它包括几个位串函数。

  • 用于mpz_tdiv_q_2exp一次将长模式右移一位，
  • mpz_tdiv_r_2exp提取最后 150 位，以及
  • mpz_hamdist找出在提取的位和短模式之间翻转的位数。

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

作为初始优化，我建议将 150 位模式按一位增量移动最多 7 位，因此您有 8 种模式可以匹配，从 150 位到 157 位。然后，不是一次移动一位长模式（这很慢并且可能在运行时占主导地位），而是一次移动 8 位。请务必清除您不想比较的位。

于 2011-04-15T16:51:00.010 回答
1

让我们称之为短位序列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)每次迭代要少得多，因此实际上它应该是有效的。

于 2011-04-15T16:24:30.277 回答
1

沿着较长的位模式移动短位模式的解决方案具有复杂度 O(N*M)（N - 短段的大小，M - 长段的大小）。

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

于 2011-04-15T18:20:49.080 回答