比较两个二进制数组与阈值（近似匹配）

Question

我有两个二进制数组，一个大小为34（模式），另一个大小为10000（目标）。 我想看看是否有任何模式在目标与阈值（如最多4个不匹配） 和返回匹配数（没有重叠发生，如果一个匹配，然后下一个匹配将远离800个单元格）。 我知道这是一种近似匹配问题，但我不知道使用哪种算法具有最佳性能。我做了什么至今：（方法LIKE2具有更好的性能）

void compare (bool *target, int t, bool * pattern , int p , int threshold) 
{ 
    for(int i =0;i<t-p;i++){ 
     if(like(target+i,pattern,p,threshold)){ 
      return true; 
     } 
    } 
    return false; 
} 

void like2(bool *target, bool * pattern , int p , int threshold){ 
    int k =0; 
    for(int i =0;i<p, ;i++){ 
     k+= target[i]^pattern [i]; 
    } 
    return (k<=threshold); 
} 
void like(bool *target, bool * pattern , int p , int threshold){ 
    int k =threshold; 
    for(int i =0;i<p,k>=0 ;i++){ 
     if(target[i]!=pattern[i]){ 
      --k; 
     } 
    } 
    return (k >=0); 
} 

我试过用字符串匹配算法，如克努特莫里斯普拉特算法，但它们是精确匹配，并改变它们近似匹配算法是一个很难的方法。

Answer 1

将模式组合成（长整数）整数pattern_int，因为它只有34位。现在循环通过target。在k = 0处，您将target位0-33组合为模式，至combined_int。当你到了k + 1重新计算combined_int如下：

combined_int = (combined_int << 1) & ~(1 << 34) | target[k + 34]; 

基本上，你一个位置（因为你提前从k到k + 1），明确转移出来的不再视为有位，并添加一个新的。

要查看匹配是否足够接近模式，请使用异或combined_int和pattern_int并计数1位。我相信后者是在现代CPU的单一指令下完成的。

编辑：当你建立初始组合，确保pattern[0]在pattern_int最终成为最显著位，同样为target。否则，您需要更改相应的combined_int重新计算的方式。