Pattern Matching for URL classification

Question

As a part of a project, me and a few others are currently working on a URL classifier. What we are trying to implement is actually quite simple : we simply look at the URL and find relevant keywords occuring within it and classify the page accordingly.

Eg : If the url is : http://cnnworld/sports/abcd, we would classify it under the category "sports"

To accomplish this, we have a database with mappings of the format : Keyword -> Category

Now what we are currently doing is, for each URL, we keep reading all the data items within the database, and using String.find() method to see if the keyword occurs within the URL. Once this is found, we stop.

But this approach has a few problems, the main ones being :

(i) Our database is very big and such repeated querying runs extremely slowly

(ii) A page may belong to more than one category and our approach does not handle such cases. Of-course, one simple way to ensure this would be to continue querying the database even once a category match is found, but this would only make things even slower.

I was thinking of alternatives and was wondering if the reverse could be done - Parse the url, find words occuring within it and then query the database for those words only.

A naive algorithm for this would run in O( n^2 ) - query the database for all substrings that occur within the url.

I was wondering if there was any better approach to accomplish this. Any ideas ?? Thank you in advance :)

Answer 1

In our commercial classifier we have a database of 4m keywords :) and we also search the body of the HTML, there are number of ways to solve this:

1. Use Aho-Corasick, we have used a modified algorithm specially to work with web content, for example treat: tab, space, \r, \n as space, as only one, so two spaces would be considered as one space, and also ignore lower/upper case.
2. Another option is to put all your keywords inside a tree (std::map for example) so the search becomes very fast, the downside is that this takes memory, and a lot, but if it's on a server, you wouldn't feel it.