Ühel kenal päeval, L, 2006-05-20 kell 01:34, kirjutas Hannu Krosing:
> Ühel kenal päeval, R, 2006-05-19 kell 18:18, kirjutas Tom Lane:
> > Hannu Krosing <hannu@skype.net> writes:
> > > I guess our regex implementation already uses boyer-moore or similar.
> > > Why not just expose the match position of substring('text' in 'regex')
> > > using some function, called match_position(int searched_text, int
> > > regex, int matchnum) ?
> >
> > If it did that might be a nice solution, but I'm not sure that it does
> > use B-M ... I can't find either "Boyer" or "Moore" in its source code.
>
> Ok, maybe it is not optimised for finding longish strings inside even
> longers trings.
>
> I had a (false ?) memory that we used some variant of pcre, and that
> pcre uses BM. I may be false on both accounts. (I know that python
> borrowed its re module from pcre).
http://www.mcabee.org/lists/snort-users/Mar-05/msg00026.html
seems to imply that PCRE uses BM at least for some case, so I might not
have been wrong in case 2 :)
> > There's no particular reason to suppose offhand that a regex engine
> > would be faster than the naive code for fixed patterns.
>
> if naive code is O(n*m), then starting from some values of n and m it is
> probably faster if it is based on somewhat optimised regex engine, the
> question is, what is the threasold and dataset for fasterness
>
--
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia
Skype me: callto:hkrosing
Get Skype for free: http://www.skype.com
