Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!jarthur!uci-ics!gateway From: schmidt@crimee.ics.uci.edu (Doug Schmidt) Newsgroups: comp.lang.c Subject: Re: Recognizing abbreviated commands using `tries' Message-ID: <25AA6CD3.16540@paris.ics.uci.edu> Date: 9 Jan 90 22:59:30 GMT References: Reply-To: schmidt@crimee.ics.uci.edu (Doug Schmidt) Distribution: comp Organization: University of California, Irvine - Dept of ICS Lines: 44 In-reply-to: scott@med.ge.com (Scott Woskoff) In article , 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