用一个阈值比较两个二进制数组(近似匹配)

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);
}

我曾尝试使用字符串匹配算法，如Knuth-Morris-Pratt算法，但他们是精确匹配和改变他们的近似匹配算法是一个困难的方式。

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上可以用一条指令完成。

EDIT:当您构建初始组合时，确保pattern[0]最终成为pattern_int中的最高有效位，target也是如此。否则，您需要相应地更改combined_int的重新计算方式。