[comp.lang.pascal] Global Searching Algorithm Needed

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