From: | Hannu Krosing <hannu(at)skype(dot)net> |
---|---|
To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
Cc: | "Jim C(dot) Nasby" <jnasby(at)pervasive(dot)com>, Mark Dilger <pgsql(at)markdilger(dot)com>, pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: text_position worst case runtime |
Date: | 2006-05-19 22:49:11 |
Message-ID: | 1148078951.3833.71.camel@localhost.localdomain |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Ü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(at)skype(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Greg Sabino Mullane | 2006-05-19 22:50:00 | Re: String Similarity |
Previous Message | Hannu Krosing | 2006-05-19 22:39:18 | Re: [OT] MySQL is bad, but THIS bad? |