Searching (was Re: Pascal vs C style string ?)

jhallen@world.std.com (Joseph H Allen) writes:
>2) Use a better algorithm for the substring search function. The
>Moyer-Fig (I'm getting the name wrong) search algorithm can be adapted to
>systems with position buffers. The algorithm goes like this:


Boyer-Moore is the correct name. This is one of my favourite algorithms;
if you modify it a tiny bit, the inner loop can be unrolled giving a 10-30%
speedup.


This works by putting 0 in the skip table for the last character in the
search string. (Incidentally, it is better to initialize your 'table' with
the actual skip count (len-x+1) instead of (x) itself.)


If you also insert the last character in the search term as a guard in the
first position after the actual buffer, the test for buffer overruns can be
removed from the inner loop as well, resulting in a single unrolled


  pos += skip[buf(pos)];


statement as the main engine.
______________________________________________________________________
Terje W Mathisen, Hydro Data, Norsk Hydro. FAX: +47-22-433606
Internet: terjem@hda.hydro.com, BIX: terjem@Bix.com
[This is swell stuff but string search algorithms are a bit far afield
from compilers topics. I've sent followups elsewhere. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.