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", ISBN 0-13-100413-1.
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.
A Trie is ultimately a recursive data structure, very similar to a tree. As the leaves of the tree, a trie has the letters of the alphabet. On each leaf may rest an element, or another branch.
A simple trie, with only one element ('snapper') in it, looks like this:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
snapper
Now, if we add 'subtle' to the Trie:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
| |
snapper subtle
And you can see that the tree grows.
There is a special case, and that is where we insert two conflicting names, such that one ends before the conflict is resolved. I refer to this as the 'at' case. For example, where we to insert 'sub' and 's' as keys into the system:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
|
sub
But where can we insert the 's'? The only conceivable spot has already been occupied by a Trie.
The solution was to create one more hole off the trie, called 'at' - which allows for this case, and allows us to hang an additional element, seperate from the array off the class.
To look up an individual element, we simply check the first letter of the key, and examine the contents of that reference. If it's an element - we're finished. If its another Trie, we must pass the request down to the next trie, so that it may check the next letter along in the string.
If the provided key is too short to uniquely match an element, it is trivial to extract the matching elements for feedback to the user. This allows for sessions such as:
-> examine sub
Multiple matches: subtle and subzero
The increased feedback that this structure makes available on a failed search is a useful feature in such an online system.
One of the better (and important) features of the trie is its dynamic growth. The trie will only ever use as much space as it needs.
The Java trie implementation owns two exception classes:
A search, even without the full key is extremely fast when compared to a hash table or the worst case linked list, for the simple reason that in most cases you don't even need a full key (string) compare.
Insertion, deletion, and iteration are relatively slow.
The trie data structure can also be huge when compared to more traditional data structures. With this consideration, I ran a small test where the names from the current Forest playerfiles (5989 names) were placed into a trie, and the results examined. There were 2,896 trie data structures created, and the mean depth of the trie search was 3.6 characters.
With these results, even with no class overhead, the trie would use the equivalent of 27 x 2896 references; this would amount to several hundred kilobytes. As a trie structure this large would only ever exist in the system in once place at any one time, this is acceptable, given that the system is not geared towards memory efficiency.
Since I expect that searching and iteration will be the more common actions on the data structure (at least in its use here), a linked list will often be used in conjunction with the trie, slowing down insertion and deletion even further, but not significantly increasing memory usage. This list can be used as a method of quickly iterating through the available elements.