🚀 go-pugleaf

Archive-name: trie-gen/1.0
Original-posting-by: schmidt@crimee.ics.uci.edu (Doug Schmidt)
Original-subject: Re: Recognizing abbreviated commands using `tries'
Archive-site: ics.uci.edu [128.195.1.1]
Reposted-by: emv@math.lsa.umich.edu (Edward Vielmetti)

In article <SCOTT.90Jan9153157@harpo.med.ge.com>, scott@med (Scott Woskoff) writes:
>I have a need to recognize one of a set of keywords, when given as
>input string either the complete keyword, the shortest prefix of the
>keyword which is unique in the set, or any string in between. The
>actual application is a command recognizer which allows the user to
>abbreviate the command names.

>Example: given the keyword set {abel, absalom}, I should get
>the following (input-result) pairs:

>	input		result
>	abs		absalom
>	absal		absalom
>	absalom		absalom
>	abe		abel
>	ab		error: ambiguous input
>	box		error: no such keyword

>The appropriate data structure seems to be a slightly modified trie.

>Because the set of keywords never changes at runtime, but does usually
>change with each release of the program, I want to build the trie at
>compile-time, using C #defines, if possible. It's not clear to me,
>however, that it is possible to do so.  A less attractive alternative
>is to build the table at runtime by inserting the keywords one at a
>time into the trie during initialization.

>Can anyone offer any help? Any alternative solutions? Good
>advice?

If you've got access to anonymous ftp you should check out the file
trie-gen-1.0.Z on ics.uci.edu (128.195.1.1).  This tar file implements
a minimal-prefix trie generator, which should do pretty much exactly
what you are looking for here.

The program is a beta-release, but there is sufficient documentation
to make it usable!

I solicit comments and suggestions for enhancements.

Doug
--
Douglas C. Schmidt