Erik Naggum <email@example.com> wrote:
| the real difference, as I see it, is that tries will be able to take
| advantage of _any_ smallest set of differences, so if you have a bunch of
| people names starting with "Smith", the trie will effectively just move
| past the first 5 and use the next 5 characters, instead.
Exactly. Plus, if you're doing typical symbol-table or other plaintext stuff,
you can *significantly* cut the amount of storage used with tries by various
forms of "compression" on each node (much like the way most C compilers
generate different styles of code for "switch" statements depending on
the pattern of "case" values), tagging each node with its "style" or kind:
- As Erik notes, you can collapse a run of fanout==1 nodes into a single
"match"-only node consisting of a string and one further node pointer.
- If the degree of fanout is >1 but still very low, the node might be
encoded as a small string that's searched sequentially, together with
a vector of the same length (indexed by the searched-for character's
position in the string). While this is a good deal slower than a pure
"radix-sort" style index, it's also *much* smaller.
- With higher fanout, a node might contain "min" & "max" character codes,
and a vector as large as "max - min + 1", indexed by "this_char - min".
- With still higher fanout, revert to a full max-char-code size vector.
In most practical applications, you'll only need a few nodes like this
(maybe even only the root node).
| a hash function would have to be excessively intelligent to adapt
| the same way.
That reminds me of a trick that can help hash tables: If you use a really
good hash, one for which nearly every bit position contains nearly a full
bit of information (a CRC-32 is such a hash), then if you store the *full*
hash value with the entry, when you want grow the hash table because the
per-bucket chains get too long, you don't have to re-hash the keys -- you
can just use more bits of the original hash value.
Finally, there's an interesting hybrid of hash tables and tries -- a
multi-level hash table that uses different bits of the hash at each level
of the tree/trie (that is, it's a binary tree if you only use one bit of
the hash per level). When you hit a leaf node you do a comparison on
the full hash first before wasting time with a full string compare.
If the hashes are the same but the strings differ, then the strings are
probably *very* different (assuming a "good" hash, such as a CRC), so
hanging a "compressed trie" (as above) off that node should be a cheap
way to resolve the conflict (that is, the strings will very likely differ
in the first character!).
[Hmmm... It would be interesting to compare these three methods for
space & speed to implement "intern"...]
Rob Warnock, 8L-855 firstname.lastname@example.org
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA