This humble, less-than-nothing monk would suggest that perhaps the original poster wishes to search the database directly with wildcarding, rather than search some database output with Perl. As much as I enjoy working with Perl, a database-based solution would likely perform better.

Oracle and MySQL have soundex functions. Postgres seems to also, as part of their fuzzystrmatch function. If your client uses Oracle and expects to do this a lot, Oracle provides function-based indices which could precompute each row's soundex value for faster response times.

Of course soundex only helps with similar words, not with related words (e.g., "boys" and "boysenberry" are similar, while "boys" and "girls" are related). The thesaurus reference sounds like a good idea in that regard.

I've had occasion to use Perl's soundex function and it works quite well, although there's some performance penalty due to the additional function calls.