Which search algorithm does GNU grep use?

I always wondered why grep is so blazingly fast?
How does grep mange the yin and yang of space and time to return results at such speed?

A quick Google search returned the result that the GNU grep uses the Boyer-Moore search algorithm.  The Boyer-Moore is basically looks first for the final letter of the target string, and uses a lookup table to tell it how far ahead it can skip in the input whenever it finds a non-matching character.

In other words, the idea behind the algorithm is to match on the tail of the pattern rather than the head, and to skip along the text in jumps of multiple characters rather than searching every single character in the text.

Therefore, in general, the algorithm runs faster as the pattern length increases.

No comments :

Post a Comment