httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sascha Schumann <sas...@schumann.cx>
Subject RE: [PATCH] Potential replacement for find_start_sequence...
Date Wed, 05 Sep 2001 10:51:53 GMT
On Wed, 5 Sep 2001, Sander Striker wrote:

> > I'm not totally sure I'm sold on this approach being better.  But,
> > I'm not sure that it is any worse either.  Don't have time to
> > benchmark this right now.  I'm going to throw it to the wolves and
> > see what you think.
>
> Me neither.  Rabin-Karp introduces a lot of * and %.
> I'll try Boyer-Moore with precalced tables for '<!--#' and '--->'.

    Well, there are more advanced algorithms than BM available
    today which are even easier to implement that the original BM
    algo.

    I'd suggest looking at BNDM which combines the advantages of
    bit-parallelism (shift-and/-or algorithms) and suffix
    automata (BM-style).

    http://citeseer.nj.nec.com/navarro01fast.html

    To give you an idea on how a bndm implementation looks like,
    I'm appending an unpolished implementation I did some time
    ago which includes a test-case for locating '<!--#'.

    - Sascha                                     Experience IRCG
      http://schumann.cx/                http://schumann.cx/ircg

Mime
View raw message