Recognizing abbreviated commands using `tries'

[Doug Schmidt]

In article <SCOTT.90Jan9153157 at harpo.med.ge.com>, scott at 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