title: How to fuzzy match a short bit pattern in a long one?
body: <p>I encounter a problem when try to match a short bit pattern in a long one: I have one long bit pattern, e.g. 6k bits, stored in a char array, also a short one, say 150 bits, stored in a char array, too. Now I want to check whether the short bit pattern is in the long bit pattern. While there is no need for short bit pattern to match some part of long bit pattern exactly, I will define a threshold, if the bit-error-rate under it, I will take the two pattern match.</p>
  
  <p>Given the misalignment problem, I can't come up with an elegant solution. One way I can find out is convert the bit pattern into char pattern, i.e. convert bit 1 to '1', 0 to '0' and apply some string matching algorithm. But I'm afraid it may cost memory 7-8 times more burden my system. Someone around me recommend the <a href="http://en.wikipedia.org/wiki/Rabin_fingerprint" rel="nofollow">Rabin Fingerprint</a>, however it seems not designed for this kind of problem.</p>
  
  <p>Hope you can give me a hand.</p>
  
  <p>Thanks and best Regards.</p>