October 1996
by Paul Mclachlan
aka subtle
A Trie, while probably not an original concept, is something I developed for the unique problem of partially matching a word, given the definitive first section of the word. For instance, if a player wished to 'examine subtle', they need only type the smallest amount of information necessary to get this across (for an unambiguous meaning).
And so, in all likelyhood, 'ex sub' could well be enough. In order to do this efficiently, I devised what I call a 'Trie', a name I adopted from the algorithm which inspired the idea, also called a Trie. (The two algorithms are effectively identical, it is really only a matter of scale).
More information on the original Trie can be found in Ian Oliver's book, "Programming Classics: Implementing the World's Best Algorithms".
My implementation of the algorithm makes several assumptions, the most important of which is that no key will ever contain non-alphabetic characters. The other assumption is that names are essentially dissimilar; that the heys contained by the database have a realtively even spread - that they're not all very close to another.
The second seems a reasonable assumption to make about the names people choose for themselves, and the second, a reasonable restriction to impose. And so we shall.