You should try some tests with urls and regexs you make up yourself, to
find out (in ballpark figures) what you can expect.

You should probably include some self-monitoring too then, and
periodically log a dump of the "top ten" slowest REs, if the scanning
process does in fact turn out to be a bottleneck.

-- Barry

Hi Steve,

Forgive me if I repeat anything you already know.

A regular expression is an expression of a set of rules that define a
"pattern" (or a pattern that defines a set of rules!).

It looks to me like you're trying to create SPAM detection rules, a most
admirable quest, and one which I am chipping away at during my own spare
time.

SPAM detection rules act as a filter, and if I'm not mistaken, you want to
filter out suspected SPAM emails.

For the greatest efficiency, you want to use the filter that removes the
most from the list in order to eliminate those from the remaining items that
need to be filtered. The fewer the items to filter, the faster the process.

Some filters will remove more than others. For example, let's say that
you're filtering on domain names. In your list, you identify the following:

^http://www.spywarerulez.com
^http://a.spywarerulez.com
^http://b.spywarerulez.com
^http://spywarerulez.com
^http://spywarerulez.net
^http://spywarerulez.org

Now, you could filter on all of them individually using several filters, but
if, for example, you know that any domain that ends with "spywarerulez."
plus a root domain, you could filter them all out with:

\b(?:http://)*\w*\.?spywarerulez.\w+\b

(Note that this assumes that the URL begins and ends at a word boundary. You
would probably want to change that part)

So, what I would do is to identify which regular expressions filter the most
items out first. Apply these filters first, and then create a succession of
more and more specific filters.

One good technique to prevent multiple filters is to use an OR expression,
as in:

\b(?:http://)*\w*\.?(spywarerulez|myspyware|spammersdelight|getrichquick|suckeraminute).\w+\b

This would match any domain with any of the domain names that are ORed
together.

yes, but you get a hit on the domain, so you proceed to the page.  If you
make the domain matching efficient, you make 95% of your matching efficient.

I disagree.  I wouldn't use your mechanism for either method.

Regex can be used not only to match, but also to parse.  Use it to parse,
but then match using a data structure.

Use regex to return a list of terms seperated by slashes.  Create a tree
structure of all of the offending pages by URL.  I'm willing to bet that 80%
of the hits against an offending page will be consumed by less than 5% of
the root elements and less than 30% of the first level elements.  In other
words, virus sites will have many virus pages, and hosting providers that
don't care about virus hosting will have many many virus sites.

allow for aliases by making your tree so that you can have references from
multiple roots point to a single tree.  This covers the fact that DNS
systems routinely allow for nearly infinite aliases.

hostingprovider.com
   subdomain: abc, jbx, sand, zx*
        dir: foo
            dir: bar
               page: viruspage1.html
               page: viruspage2.html
               page: viruspage3.html
            dir: fudge
               page: viruspage4.html
hostalias.com -- reference to hostingprovider.com
127.198.41.77 -- reference to hostingprovider.com

One regex can parse your entire URL into parts.  Domain, subdomain, a list
of directories, and a page reference, followed by a list of parameters.
So you can match once against every URL, take the parts list and run it
through the tree you create.  Simple matching will catch every hit.  And it
scales well.

Let's say that you have 10,000 URLs in your list.  Let's say that 80% of
them have the same 100 domains.  That leaves 20% with a smattering of other
domains.  I'll swag that down to about 1000 domains.  Let's say that you
create a tree structure like above, but the root is a sorted list of these
1000 domains.  Let's say you use my method and a binary search against the
domain name.  You can find the domain hit in 10 hits or less... you'll
average five hits.  Then, if your directory and page lists follow the same
pattern, you are likely to find your match or free the URL in less than 10
more matches.  That's 20 matches.  Add another 10,000 URLs to the list.  The
number of matches goes up... to 21.

With your method, the first scenario requires 10,000 matches.  The second
requires 20,000 matches.  It scales EXCEEDINGLY badly.

Please, Steve, use a data structure for this mechanism.  The fundamental
concept is a Suffix tree, which is a specialized form of a Trie.  Note that
you could use a pure Trie structure, especially a Patricia Trie structure,
if you are clever and want REALLY fast performance, but that may require
some programming chops.  You can find a good writeup on Trie structures on
wikipedia.  http://en.wikipedia.org/wiki/Trie  You could also use a Directed
Acyclic Word Graph, which will give you some very fast performance as well.
To be honest, I may have described a compact DAWG above.

Some other links:
http://www.nist.gov/dads/HTML/suffixtree.html
http://www.nist.gov/dads/HTML/directedAcyclicWordGraph.html