[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: freshman-level Boyer-Moore fast string search

This page is part of the web mail archives of SRFI 75 from before July 7th, 2015. The new archives for SRFI 75 contain all messages, not just those from before July 7th, 2015.

On 7/29/05, Alex Shinn <alexshinn@xxxxxxxxx> wrote:
> Is the three-stage assumption for binary trees?  That would suggest
> the search strings are never longer than 8 characters.  In practice I
> frequently search for much longer strings - "call-with-current-continuation"
> at 30 characters (5 stage lookup) is fairly common, and mult-line
> searches are not unheard of.  You can't just dismiss a lg(m) factor.

Oops, that was careless.  The real cost depth is proportional to the
log of the number of distinct characters, 13 distinct characters for
call-with-current-continuation for a 4 stage lookup.