rcj@attctc.Dallas.TX.US (Robert Johnson) (11/16/89)
I am in need of an efficiant global searching algorith, preferably in pascal, but simply a good method of opperations would be appreciated. What I mean by a 'global searching alogorithm' is what free form databases (i.e. Broderbund's MemoryMate [great program, BTW]) use to search through uncorrolated free form data to find the key. If I am making any sense at all (I doubt it, I know what I'm talking about though, just not how to do it!), then I would really appreciate some pointers. Thanks, Robert C. Johnson -- | Robert C. Johnson | "Minds are like parachutes. | | rcj@attctc.dallas.tx.us | They only function when they are | | (214) 357-5306 | Open." -Sir James Dewar |
sccowan@watmsg.waterloo.edu (S. Crispin Cowan) (11/17/89)
In article <10213@attctc.Dallas.TX.US> rcj@attctc.Dallas.TX.US (Robert Johnson) writes: >I am in need of an efficiant global searching algorith, preferably in >pascal, but simply a good method of opperations would be appreciated. >What I mean by a 'global searching alogorithm' is what free form >databases (i.e. Broderbund's MemoryMate [great program, BTW]) use to search >through uncorrolated free form data to find the key. If I am making any >sense at all (I doubt it, I know what I'm talking about though, just >not how to do it!), then I would really appreciate some pointers. Sort of like grep? Is that what you really want, or am I missing something? If grep is what you want, but it isn't fast enough, professors Gaston Gonnet and Frank Tompa here at waterloo have developed some algorithms called PAT, that were used in developing the computerized New Oxford English Dictionary. They suck in the raw text, pre-process it a bit, and spit out some index files. Whtih these index files, they cn then search for strings in log(n) time, and regular expressions in sub-linear time. >| Robert C. Johnson | "Minds are like parachutes. | >| rcj@attctc.dallas.tx.us | They only function when they are | >| (214) 357-5306 | Open." -Sir James Dewar | ---------------------------------------------------------------------- Login name: sccowan In real life: S. Crispin Cowan Office: DC3548 x3934 Home phone: 570-2517 Post Awful: 60 Overlea Drive, Kitchener, N2M 1T1 UUCP: watmath!watmsg!sccowan Domain: sccowan@watmsg.waterloo.edu "We have to keep pushing the pendulum so that it doesn't get stuck in the extremes--only the middle is worth having." Orwell, Videobanned -- Kim Kofmel
reino@cs.eur.nl (Reino de Boer) (11/17/89)
rcj@attctc.Dallas.TX.US (Robert Johnson) writes: >I am in need of an efficiant global searching algorith, preferably in >pascal, but simply a good method of opperations would be appreciated. You might want to investigate the Knuth-Morris-Pratt string search algorithm (easy explanation in R. Sedgwick - Algorithms). Reino -- Reino R. A. de Boer Erasmus University Rotterdam ( Informatica ) e-mail: reino@cs.eur.nl