c++ - 将两个二进制数组与阈值进行比较(近似匹配)

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 上通过单条指令完成的。

编辑:构建初始组合时，确保pattern[0] 最终成为pattern_int 中的最高有效位，并且同样适用于 target。否则，您需要相应地更改 combined_int 的重新计算方式。