kalra@cit-vax.Caltech.Edu (Devendra Kalra) (07/06/88)
Could someone point me to references to efficient methods to carry out wild card searches for records that match. Wild card patterns could be in general any regular expressions. References to more restricted patterns also welcome. Thanks Deven
jbrown@jplpub1.jpl.nasa.gov (Jordan Brown) (07/07/88)
In article <7158@cit-vax.Caltech.Edu> kalra@cit-vax.UUCP (Devendra Kalra) writes: >Could someone point me to references to efficient methods to carry out >wild card searches for records that match. > >Wild card patterns could be in general any regular expressions. References >to more restricted patterns also welcome. Kernighan and Plauger talk about it in Software Tools. No doubt there are other, more scholarly, references, but ST is pretty practical. I use a simple obvious recursive algorithm to do * and ? matching like the shell does (but not []), and it's quite acceptably fast when you consider that it doesn't really have to recurse often, and there's a lot of overhead involved in record fetches.
kalra@cit-vax.Caltech.Edu (Devendra Kalra) (07/07/88)
I posted a query a few days ago about wild card searches. I think I was not quite clear as to what I am looking for. I am NOT looking for an algorithm to see if given a string s1 and a regular expression s2, whether s1 and s2 match. What I am looking for is implementation of wild card searches for data bases. More specificaly, given n records, I want to fetch the records the mth field of which match a given regular expression. I am looking for ways of organizing and accessing data records to do this in an efficient way. I would not like to compare each record for a match. It seems to me that methods like hashing and index files do not work for wild card patterns. Any ideas? Deven