Hacker News Reader

Comment by rntz | Hacker News Reader

Boyer-Moore is a great algorithm, but it's for fixed-string searching. grep, in the general case, handles regular expression searching. Is there some way to extend Boyer-Moore to regular expressions that I'm unaware of? Or is GNU grep's use of Boyer-Moore limited to when the search string is just a literal?

View on HN

In practice, most regular expressions contain some literal strings. You can use Boyer-Moore to anchor the match, then do a full regexp match from there.

..and the classical answer to implementing full Regex is finite state automaton, correct? At least, there is a one to one correspondence.

I'm curious, though, about what tricks are used in actual implementations to speed things up, and what modern Regex features necessitate climbing further up the Chomsky Hierarchy. (I seem to recall reading about features getting slipped into Regex engines that made them no longer finite state, but can't recall what they were, right now.)

http://en.wikipedia.org/wiki/Shift-or

Check out Shift-Or: used in agrep, and another example of a very clever algorithm. Rather than translating a non-deterministic finite state automata to a deterministic one, it uses the boolean operations of the hardware to simulate the NFA directly. Result: linear time regexp for patterns that have less than the bit-length of a machine's registers. I.e., 32 bytes on x86, 64 bytes on x86_64, etc.

Back-references are the most common feature in regexp engines that make them non-regular.

From further into the email thread:

Given a regex such as /foo.*bar/ grep can search on 'foo' and then apply the Boyer-Moore algorithm. (http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...).

Given a regex with multiple fixed-strings the longest will be used. (http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...)

Reply on news.ycombinator.com