schmidt@crimee.ics.uci.edu (Doug Schmidt) (01/10/90)
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