Re: cvs: php4 / NEWS /ext/standard string.c

At 05:25 AM 7/21/2001 +0200, Sascha Schumann wrote:

Yes it is difficult to tell because it is not only a function of the length of the pattern but also a function of what characters and sub-strings have a tendency to repeat themselves and what sub-strings you are likely to search for. Actually the latter is what ends up effecting if a long or short pattern is more efficient.

    I think I might drop Boyer-Moore alltogether.  While looking
    for Smit's paper on BM, I found various papers concerning
    advancements in this area.  A report by Baeza-Yates[92]
    describes a Shift-Or algorithm which is superior to BM in
    almost any case while being of less complexity.  I'm
    currently reading Navarro[98] which claims to combine the
    aspects of various algorithms while being even simpler to
    implement.

    Baeza-Yates, 1992, A New Approach to Text Searching
    Navarro, 1998, Fast and Flexible String Matching by Combining
    Bit-parallelism and Suffix Automata

OK cool. Personally I'd like to know what your conclusion ends up being. I don't have time to read all these papers but it's definitely an interesting topic. The problem is producing test cases because of the strong link between the common strings & sub-strings in PHP specifically. This is of course unless another algorithm is literally 90% of the time faster than the dumb approach. Then it is worth converting. Andi