trie-gen.1

早期freebsd实现

.TH TRIE-GEN 1 "12 December 1989" "Version 1.0"
.de BP
.sp
.ti -.2i
\(**
..
.SH NAME
trie-gen \- generate a minimal-prefix trie
.SH SYNOPSIS
.B trie-gen
[
.B \-c
] < keyfile
.SH DESCRIPTION
.I 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 implementations 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:

.nf
----------------------------------------
bash
bison
diff
diff3
egrep
flex
g++
gawk
gcc
gdb
genclass
gnuchess
gnuplot
gperf
grep
indent
make
sed
----------------------------------------
.fi

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.

.I 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 
.I n 
is the number of user-specified keywords from the standard input and
.I 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 
.I r 
is the total number of rows in the generated trie, 
.I 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.

.SH OPTIONS

.TP
.B \-c
Compact the generated trie using a technique called `double-offset
indexing,' which is used in Bison and FLEX (also described in Tarjan
and Yao's article ``Storing a Sparse Table'' in CACM, 1979).
.B \-f
Generates a `full' trie rather than a minimal-prefix trie.
.SH "SEE ALSO"
gperf (the GNU perfect hash function generator)
.SH 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
.BR [e-mail] .
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.
.SH COPYING
Copyright (c) 1989 Free Software Foundation, Inc.
.P
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.
.P
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
permission notice identical to this one.
.P
Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that this permission notice may be included in
translations approved by the Free Software Foundation instead of in
the original English.
.SH AUTHORS
Douglas C. Schmidt ([e-mail])