[boyter]

Interesting solution. I did something a little different for searchco.de when I was implementing regex search.

Essentially I took the regex such as [cb]at and then expand it out to get all of the terms, in this case cat and bat and then do a standard fulltex search based on those terms to get as close a match as possible. I then loop over the results to get back those which are exact matches.

Its actually more complex then that but with some other trickery (infix and prefix indexing) but it works reasonably well although I am still ironing out some kinks.

[ww520]

Interesting.

  What does the wildcard match "foo.*bar" expand to?
  How do you handle those pathological cases like "f.*r"?

Edit: HN can't displaying the wildcard char. Reformat it.

[boyter]

Much of the same. Most indexers these days allow a proximity search. So you can expand out "foo.bar" into the search "foo << *bar".

It is less likely to pick up things like "fooabar" but assuming there are still results like "foomanchu bar" they will be found. Also assuming the default for your proximity search is OR logic you should still pick up "foobar" eventually.

As for the other case you will naturally find all sorts of things that match. But as with the method in the article the more information you give it the closer a match you will find.

I don't know if the best/worst case is any better then the linked but it does work reasonably well.