Did you have a look at agrep?
agrep supports many kinds of queries including arbitrary
wild cards, sets of patterns, and in general, regular
expressions. See PATTERNS below. It supports most of the
options supported by the grep family plus several more
(but it is not 100% compatible with grep). For more
information on the algorithms used by agrep see Wu and
Manber, "Fast Text Searching With Errors," Technical
report #91-11, Department of Computer Science, University
of Arizona, June 1991 (available by anonymous ftp from
cs.arizona.edu in agrep/agrep.ps.1), and Wu and Manber,
"Agrep -- A Fast Approximate Pattern Searching Tool", To
appear in USENIX Conference 1992 January (available by
anonymous ftp from cs.arizona.edu in agrep/agrep.ps.2).
Regards,
Marc