Recognizing abbreviated commands using `tries'

[Scott Woskoff]

I'm posting this for a friend, so please reply directly to him at:

	uunet!crdgw1!gemed!pete

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?

Peter Schiltz
CSE, W-824
GE Medical Systems
3200 N. Grandview
Waukesha WI 53188
uunet!crdgw1!gemed!pete