Fast regular expressions

[Jeff]

It seems to me that supporting fuzzy matching in a general regular 
expression library would add a whole lot of complexity that wouldn't be 
used by many people. I think it would be hard to justify this.

Were you really adamant about having regular expression matching, or 
more focussed on simple fuzzy matching? There are probably some 
libraries already that can search for fuzzy matches pretty well.

If you can't find anything that meets your needs, you might consider 
having a look at http://en.wikipedia.org/wiki/Bitap_algorithm and 
http://en.wikipedia.org/wiki/Levenshtein_distance - they could be useful 
if you decide to write your own.