Articles tagged “Algorithm”

Tries and Text::Match::FastAlternatives

I’ve just released version 1.00 of my Text::Match::FastAlternatives Perl module. Since I’m apparently declaring it stable, I thought it was worth writing up a description of what it does, and how it does it.

Suppose you have a large list of strings, and a set of keys, and you need to determine, for each of the strings, whether any of the keys occur in it. For example, the list of strings might be a list of user-agent headers sent to a web server, and the keys a set of strings that are good indicators of robots accessing your site; you want to calculate some server statistics, but disregard any robotic traffic.

How do you go about doing that?


Regex matching algorithms and asymptotic run time

[Previously published here.]

Russ Cox recently wrote an article about the worst-case run time of two different implementation strategies for matching regexes: Thompson NFA, and backtracking NFA. In particular, Russ points to the Perl regex engine as an example of how not to do it.

The article’s an interesting read. But I don’t think the approach described is necessarily easy and/or useful to fit into Perl, though.