[MUD-Dev] Re: Question on c++ switch optimization, and parsers in general.

[T. Alexander Popiel]

In message:  <199902090353.UAA00877 at ami-cg.GraySage.Edmonton.AB.CA>
             Chris Gray <cg at ami-cg.GraySage.Edmonton.AB.CA> writes:
>
>However if you insist on minimal unambiguous abbreviations, and don't
>want a linear search, how about this:
>
>At startup time, scan your table of commands, and build some auxilliary
>data structures. Have the code determine the minimum unambiguous form
>of all commands. Enter all of those into a hash table (could even try
>a mostly minimal one). Include in your data structures the full name
>of the commands. Then, lookup consists of looking up longer and longer
>portions of the input command until you find a match, or you have tried
>the full command. Search is O(length of input command) rather than
>O(number of commands).

Better yet, just store your commands in a compressed radix tree.
(Treat the command string as a bit string, going left or right
based on 0 or 1 in a given position; when building the tree,
omit levels where there is no branch.  Internal tree nodes tell
which bit to test, commands are in leaves.  You can optimize
by testing more than 1 bit at a time and having a larger branching
factor.)  Just walk the tree until you reach the end of input
or hit a leaf.  If you run out of input before reaching a leaf,
then the input was ambiguous.  If you reach a leaf, check the
input against the command you found, to see if they typed garbage
which just looked somewhat like a command (weird things can happen
with the tree compression).  If you're using a higher branching
factor and walk off the tree, then they entered a bogus command.

Search is at most O(length of input command) (and is frequently
less), typos tend to fail early instead of testing every possible
prefix, and you don't have to reprobe a hash table or figure out
minimum non-ambiguity.  The tree-insert code is a bit of a pain,
though.

- Alex