trie-gen man page on 4.4BSD

Man page or keyword search:  
man Server   1065 pages
apropos Keyword Search (all sections)
Output format
4.4BSD logo
[printable version]

TRIE-GEN(1)							   TRIE-GEN(1)

       trie-gen - generate a minimal-prefix trie

       trie-gen [ -c ] < keyfile

       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:


       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.

       -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

       gperf (the GNU perfect hash function generator)

       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  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.

       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.

       Douglas C. Schmidt (

Version 1.0		       12 December 1989			   TRIE-GEN(1)

List of man pages available for 4.4BSD

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
Vote for polarhome
Free Shell Accounts :: the biggest list on the net