私は1と0の特定の文字列を持っており、最大20％のエラーで他の文字列で最も適切な文字列を探したいとします。

Question

たとえば、次の0と1の文字列が与えられます：001011. This私のパターン、つまり文字列Aです。 次に、0と1の長い文字列B（例：010100010010010）が与えられました。私の仕事はBの文字列Aの最も適切な文字列を見つけることです。最も適切な文字列である必要はないため、最大20％の誤差がある可能性があります。

たとえば、文字列Aの場合は01001、一致率が11001の場合は文字列の80％ Bは最初のビットを除いて文字列Aと一致します。同じA文字列の場合、11101はそれの60％しか一致しません（最初と最後のビット11101のirdの位置は、Aの最初と3番目のビットと一致しません。これは欲望の解決策ではありません。

Nが文字列Aのビット数である場合は、BのN長シーケンスを一度にチェックすることを意味します（Bの評価ビットは連続した位置になければなりません。 B）。例： A-01011とB-010100100111とします。最初にシーケンス01010（非常に最初の位置から始まるBの最初の5ビット）、次に10100（Bの2番目のビットで始まる最初の5ビット）を評価します。この例では、01010では4ビットのみがAと一致し、01010は80％の一致であることを示しています。 10100に関して、ビットはAと一致しないので、0％の一致である。

Aが01001でBが01101の場合があります（Bの最初の2ビットはAの最初の2ビットと一致し、Bの最後の2ビットは最後の2ビットAと一致します）。したがって、それは80％のマッチです。 AがBよりも長い場合

は、その後、Aは、私は、この問題を攻撃するための戦略を、アルゴリズムを知っていただきたいと思い

---

B.

で一致していません。私はこの問題を可能な限り明確にしたいと思っています。そうでない場合、私はあなたにさらなる説明を提供するよう修正します。私はこの問題が実際にパターンマッチングに関して実際のアプリケーションを持つかもしれないと仮定します。 私は解決策が必要であり、私は可能な限り説明を改善することを楽しみにしています。

Answer 1

実際には2進数を比較するだけです。したがって、文字列を数値に変換してバイナリを比較してください。だから、（これはHow to compare two bit values in C?から取られている。多分、この重複を？）

0^0 = 0 
1^0 = 1 
0^1 = 1 
1^1 = 0 

11001^11101 = 00100

（Cで^）、XORビット演算（ https://en.wikipedia.org/wiki/Bitwise_operation）を使用します。

追加パイソンのコード、おそらく最適ではないが、これは（LEN（b）の-len（A））に比例し

def bitcount(n): 
count=0 
while(n): 
    count+= (n & 1)  
    n >>=1 

return count 

a="01011" 
b="010100010010010" 

number= int(a, 2) 
new = [] 
result=[] 
for i in range(0, len(b)-len(a)): 
    new.append(int(b[i:i+len(a)],2)) 

    compare = number^new[i] 

    if(bitcount(compare) < int(0.2*len(a))+1): 
     print(b[i:i+len(a)]) 

便利かもしれません*（a）のlenを、私は思います。 O（a b）私が間違っていれば私を修正しますか？..