Re^5: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?)

I mean literally convert the bits to bytes. The stream of 8 bits -> 1 bytes. Then take the needles and convert them to bytes (as well as shifting the needle bits out to cover the unaligned issue) 8 gb bitstring to 1 gb of bytes string. needle

11101110 01101001 to
11011100 11010010
11011100 11010011
10111001 10100110
10111001 10100111
... x 8 bit variations. 

Convert them to bytes and then use one of the string efficient algos. 
+ Matches on the needle will allow you to either know 100% (if its on 
+the non shifted bytes) or at least that there is a possible match on 
+the shifted bytes which can be verified at the bit level for the full
+ match.
[download]

Comment on Re^5: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) Download Code

Replies are listed 'Best First'.
Re^6: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by Anonymous Monk on Apr 06, 2015 at 06:31 UTC
the shift is basically giving you string needles that represent all of the alignments possible.	[reply]