TRIE-GEN(1)TRIE-GEN(1)NAMEtrie-gen - generate a minimal-prefix trie
SYNOPSIStrie-gen [ -c ] < keyfile
DESCRIPTION
TRIE-GEN is a program that reads a user-specified set of keywords from
standard input and generates a minimal-prefix trie. Minimal-prefix
tries have several useful properties that make them efficient implemen‐
tations for static search sets. The table-driven trie generated by
TRIE-GEN recognizes keywords in the search set in time proportional to
the length of the shortest unambiguous prefix for a given keyword.
Consider a command interpreter for an interactive debugger or operating
system shell (e.g., gdb or VMS). It is frequently nice to allow users
to type the `minimal unambiguous prefix' for any command in the set of
built-in keywords. For example, given the following complete list of
system commands:
----------------------------------------
bash
bison
diff
diff3
egrep
flex
g++
gawk
gcc
gdb
genclass
gnuchess
gnuplot
gperf
grep
indent
make
sed
----------------------------------------
and assuming these are the only available commands, a user could invoke
the egrep program simply by entering a single `e', but would need to
enter `ba' to run bash or `gnuc' to run gnuchess.
TRIE-GEN generates several static lookup tables and two functions that
allow client programs to either interpret standard input one character
at a time or, given a prefix string, to determine which keyword in the
static search set this prefix string matches.
The trie generation algorithm runs in time proportional to O(n * k),
where n is the number of user-specified keywords from the standard
input and k is the length of the longest common prefix between any
words in the keyword set.
The table compaction algorithm, invoked by giving the `-c' option, runs
in time proportional to O(r * e * 128), where r is the total number of
rows in the generated trie, e is the maximum number of non-null entries
in each row, and 128 is the size of the ASCII character set used to
index into the trie.
OPTIONS-c Compact the generated trie using a technique called `double-off‐
set indexing,' which is used in Bison and FLEX (also described
in Tarjan and Yao's article ``Storing a Sparse Table'' in CACM,
1979). -f Generates a `full' trie rather than a minimal-prefix
trie.
SEE ALSO
gperf (the GNU perfect hash function generator)
BUGS
None known at this time, though there is much work to be done with the
user interface and program options... Bugs should be reported to
schmidt@ics.uci.edu. Bugs tend actually to be fixed if they can be
isolated, so it is in your interest to report them in such a way that
they can be easily reproduced.
COPYING
Copyright (c) 1989 Free Software Foundation, Inc.
Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.
Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided that the
entire resulting derived work is distributed under the terms of a per‐
mission notice identical to this one.
Permission is granted to copy and distribute translations of this man‐
ual into another language, under the above conditions for modified ver‐
sions, except that this permission notice may be included in transla‐
tions approved by the Free Software Foundation instead of in the origi‐
nal English.
AUTHORS
Douglas C. Schmidt (schmidt@ics.uci.edu)
Version 1.0 12 December 1989 TRIE-GEN(1)