比較兩個二進制數組與閾值（近似匹配）

我有兩個二進制數組，一個大小爲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); 
}

我試過用字符串匹配算法，如克努特莫里斯普拉特算法，但它們是精確匹配，並改變它們近似匹配算法是一個很難的方法。

來源

2015-08-23 abdolahS

當'k'已經超過閾值時加入提前返回 – timrau

它不會提高性能！ – abdolahS

@abdolahS你是什麼意思，如果有一場（接近）比賽，那麼下一場比賽至少會有800「小格」？你是否貪婪地從左到右搜索大串中的（接近）比賽，然後如果你找到一個，那麼你在大串中向右移動800個位置來尋找下一個接近的匹配？ – user2566092

將模式組合成（長整數）整數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重新計算的方式。

來源

2015-08-23 19:24:12 doublep

謝謝，這是一個很好的答案，但模式長度超過長位長度的情況怎麼樣？（例如100位而不是34位） – abdolahS

您可以通過使用'combined_int'和'pattern_int'幾個整數（或一列整數），並將一位從低位移到高位。但是，性能也會下降，但是對於兩個整數（100位），它應該比逐個元素的解決方案更好，我猜。但總的來說，這並沒有太好地擴大，是的。它通常取決於元素內部循環的預期大小。總體而言，模式大小比例的閾值越大，我描述的按位算法越好。 – doublep

@abdolahS - 有幾個128位寄存器，如果這對您有用。 –

比較兩個二進制數組與閾值（近似匹配）

回答

相關問題