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

My gut feeling on this one is that brute force is the only way, _but_ processors are really good at bit-ops so it should be possible to do well.

However I think that to do it efficiently you'll need to get closer to the processor then the high level languages will allow, so you will have to write it in assembler. On x86 there are the MMX instructions that let you operate on 64 bits at a time, which might help.

Another thought: GPUs must be really good at shifting bits strings and doing bit-ops, so maybe some smart code running on your graphics card will do the job :). I'm thinking about opengl / cuda etc. But as I have other things to do today, I trying desperately NOT to fall down that rabbit hole right now! When I get time I'll have a read around the subject, it sounds really interesting.

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

Replies are listed 'Best First'.
Re^2: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by BrowserUk (Patriarch) on Apr 05, 2015 at 13:23 UTC
On x86 there are the MMX instructions that let you operate on 64 bits at a time, which might help. I already posted a very efficient brute-force algorithm that uses 128-bit shifts to good effect. The main purpose of this meditation was to try and discover if there are any smart bit-string search algorithms that I haven't discovered; as well as demonstrate that the fast string search algorithm don't work. GPUs must be really good at shifting bits strings and doing bit-ops That's the kind of thing that is a possibility. Thanks. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked	[reply]

Replies are listed 'Best First'.

Re^2: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?)
by BrowserUk (Patriarch) on Apr 05, 2015 at 13:23 UTC

On x86 there are the MMX instructions that let you operate on 64 bits at a time, which might help.

I already posted a very efficient brute-force algorithm that uses 128-bit shifts to good effect.

The main purpose of this meditation was to try and discover if there are any smart bit-string search algorithms that I haven't discovered; as well as demonstrate that the fast string search algorithm don't work.

GPUs must be really good at shifting bits strings and doing bit-ops

That's the kind of thing that is a possibility. Thanks.

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

[reply]