Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!umich!yale!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!math.lsa.umich.edu!emv From: schmidt@crimee.ics.uci.edu (Doug Schmidt) Newsgroups: comp.archives Subject: [comp.lang.c] Minimal-prefix trie generator Message-ID: <10595@stag.math.lsa.umich.edu> Date: 10 Jan 90 01:04:09 GMT References: <25AA6CD3.16540@paris.ics.uci.edu> Sender: news@math.lsa.umich.edu Reply-To: schmidt@crimee.ics.uci.edu (Doug Schmidt) Followup-To: comp.lang.c Lines: 49 Approved: emv@math.lsa.umich.edu (Edward Vielmetti) 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@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