Predicting the number of nodes in a trie with uniformly distributed strings

A trie is a type of tree that stores strings. Each character of the strings is a node and strings that share a common prefix also share the nodes, which means that a common prefix is only stored once, reducing some redundancy. But how much space is saved by using a trie? In order to answer this question, first we have to calculate the expected number of nodes a trie will have for "n" strings of "m" characters each with "c" possible characters (character set).

Consider the following diagram of a trie that contains the words "me", "if", "in", and "it". In it we have added a new word "my".


The word "my" only required the creation of one new node, since its first letter already existed in the word "me" so that node was shared and not recreated. In general, if a string is inserted in a trie, the number of new nodes created depends on the length of the longest existing prefix in the trie. This length will be the number of nodes that will be shared/reused. The remainder of the string will require new nodes for each character. If the whole string already exists then there will be 0 new nodes whilst if the string is completely new with no existing prefix then there will be a new node for each character. Specifically, for a string of length "m" whose longest existing prefix is of length "p", the number of new nodes created will be "m - p".

The equation we need to figure out looks like the following:

expected number of nodes = (m)(expected number of strings with prefix of length 1 not found)
                           + (m-1)(expected number of strings with prefix of length 2 not found)
                           + (m-2)(expected number of strings with prefix of length 3 not found)
                           + ...
                           + (1)(expected number of strings with prefix of length m not found)

Assuming that the strings are generated using a uniform distribution (any character can appear anywhere in the string), we need to find the expected number of strings out of "n" inserted strings made from "c" possible characters that will have a non-existing prefix of length "p".

This is basically the expected number of strings being selected for the first time when "n" selections are made from among all possible "p" length strings made from "c" possible characters (there are "c^p" possible such prefixes). This is equivalent to saying that it is the expected number of non-collisions when randomly placing "n" objects in "c^p" slots.

In my previous post, I showed that the expected number of collisions when randomly placing "n" objects in "s" slots is
n - s(1 - (1 - 1/s)^n)
which means that the number of non-collisions is
n - (n - s(1 - (1 - 1/s)^n))
which simplifies to
s(1 - (1 - 1/s)^n)
which when we plug in our values becomes
(c^p)(1 - (1 - 1/(c^p))^n)

But there's a problem. The above equation tells you the expected number of non-collisions when considering "p" length prefixes. But consider the previous diagram again. If the word "he" was added, it is true that the length 2 prefix of the word ("he") does not result in a collision, but this does not mean that just 1 new node will be added. In reality, 2 new nodes will be added because it is also true that its length 1 prefix ("h") will also not result in a collision. What this means is that the equation will not give the number of strings which will not result in a collision due to their length "p" prefix only, but also due to their length "p-1" prefix, which is not what we want. To fix this, we subtract from the equation the number of non-collisions due to the shorter prefix:

expected number of strings with prefix of length p not found = (c^p)(1 - (1 - 1/(c^p))^n) - (c^(p-1))(1 - (1 - 1/(c^(p-1)))^n)

Of course this does not apply for the length 1 prefix, so we need to be careful to only apply the subtraction for prefix lengths greater than one.
(You might think that we need to subtract for each shorter prefix length, but when this was tried the result became a negative number. Perhaps some form of inclusion-exclusion principle needs to be applied. Using this equation, the result matches empirical data for many different parameters.)

So, continuing from our earlier equation,

expected number of nodes = (m)((c^1)(1 - (1 - 1/(c^1))^n))
                           + (m-1)((c^2)(1 - (1 - 1/(c^2))^n) - (c^(2-1))(1 - (1 - 1/(c^(2-1)))^n))
                           + (m-2)((c^3)(1 - (1 - 1/(c^3))^n) - (c^(3-1))(1 - (1 - 1/(c^(3-1)))^n))
                           + ...
                           + (1)((c^m)(1 - (1 - 1/(c^m))^n) - (c^(m-1))(1 - (1 - 1/(c^(m-1)))^n))
= sum( c^i - c^i*((c^i-1)/c^i)^n for i in 1..m )

In Python code this becomes:

from fractions import Fraction
def exp_num_trie_nodes(n,m,c):
    return float(sum( c**i - c**i*Fraction(c**i-1,c**i)**n for i in range(1,m+1) ))

Rate of change

Here is a comparison of how the number of nodes increases depending of which variable (n,m,c) is changed:



As "n" increases, the number of nodes added starts slowing down, which makes sense since the more strings there are, the more existing prefixes can be reused. As "m" increases, the number of nodes added starts speeding up and then becomes linear, which makes sense too since longer strings are sparser and thus it would be harder to find a matching prefix which is long from among 100 strings. As "c" increases, the number of nodes added shoots up until a point where it then slows down, almost like it is logarithmic. This is because after a point it will not matter how rare the strings are since there are only 100 strings to choose from among the "c^m" possible strings. Since the length is not increasing, the same number of nodes will be used.

Size of trie

So does using a trie compress a set of strings? Keep in mind that a node takes more space than a character since it needs to point to other nodes whereas strings are arrays without pointers. We'll assume that all strings are the same length in order to reduce the number of variables. This will reduce the amount of information needed for both the set of strings and the trie (no need to include terminator flags for the strings) and the number of strings of maximum length is greater than the total number of shorter strings so it will not be a significant error in representation.

Call the number of nodes in the trie "N(n,m,c)".

The size of the normal set of strings is as follows:
n(m log(c))
where "log(c)" is the size of each character (the number of bits needed to represent each character). Of course this assumes that each string is unique. Tries only store unique strings and the way we compute the number of nodes does not assume that the strings will be unique. So we need to subtract the expected number of repeated strings from among those "n" strings. The number of repeated strings is equal to the number of collisions when placing "n" objects in "c^m" slots.

Array of strings: n(m log(c)) - (n - (c^m)(1 - (1 - 1/(c^m))^n))

The size of the trie is as follows:
N(n,m,c)(k(log(c) + log(N(n,m,c))))
where "log(c)" is the size of each character (the number of bits needed to represent each character), "log(N(n,m,c))" is the size of a pointer (which at minimum would be the logarithm of the number of nodes), and "k" is the number of pointers used on average per node. Given that the majority of the nodes in a trie will be leaf nodes, the majority of nodes will not have children. In fact the average will be less than one child per node. If arrays are used, "k" must be equal to "c", but if a linked list is used then "k" is the average but we have to also include the linked list pointer size with each character. The pointer size of the linked lists can be assumed to be "log(N(n,m,c))" since the total number of child nodes is equal to the number of nodes (minus the root node).

Array based: N(n,m,c)(c(log(c) + log(N(n,m,c))))

Linked list based: N(n,m,c)(k(log(c) + log(N(n,m,c)) + log(N(n,m,c))))

Here is a graph showing how the set of strings, array based trie, and linked list based trie increase in size with "n" when "c" is 5, "m" is 5, and "k" is 0.9:



It is clear that an array based trie cannot be used to compress a collection of strings as nodes take too much space. But what if we changed the value of "k" in the linked list based trie?



This shows that unless you have an average number of children per node of 0.2 or less, the array of strings will always take less space. Notice that this says nothing about tries which attempt to minimize the number of nodes such as radix trees where a single node represents a substring rather than a character. Also notice that this is about uniformly distributed strings, not linguistic strings which have a lot of redundancy. In a future post I shall make empirical comparisons on linguistic data.

Translating an arbitrary integer into a circular array index

A circular array is an array which is connected at the edges, that is, it has no beginning or end and traversing the array will eventually get you back to where you started. Of course in practice a normal array is used and the given index is mapped into a valid array index. This is usually done using modulo operations (the remainder after dividing the index by the array length). But what if you need to also allow negative indexes?

Let's say you have an array of length 5 and you want to use it as a circular array.

0

1

2

3

4

If you start at index 2 and move 1 to the right then you end up in index 3. But if you move 3 to the right you end up in index 0. On the other hand if you move 3 to the left then you end up in index 4. Here are some other examples of this translation:

Starting index	Add to it	Resultant	Translated index
2	+1	3	3
2	-1	2	2
4	+1	5	0
0	-1	-1	4
2	+3	4	0
2	-3	-1	4
2	+7	9	4
2	-7	-5	0
2	+15	17	2
2	-15	-13	2

We need a general formula to map arbitrary resultant integers into corresponding indexes. The modulo operator will not map negative numbers correctly:

6 % 5 = 1
5 % 5 = 0
4 % 5 = 4
3 % 5 = 3
2 % 5 = 2
1 % 5 = 1
0 % 5 = 0
-1 % 5 = -1
-2 % 5 = -2
-3 % 5 = -3
-4 % 5 = -4
-5 % 5 = 0
-6 % 5 = -1

This is because if the whole number division of a negative number N divided by a positive number P is D, then the remainder would be the number X such that D*P + X = N holds. For example, 4/5 = 0 remainder 4, because 0*5 + 4 = 4. Another example, -4/5 = 0 remainder -4 because 0*5 + -4 = -4.

Now in order to get a mapping from arbitrary resultant integers to corresponding indexes in a circular array we need to use the following formula:

Given a resultant R and a length of array L, the corresponding index is

(R%L + L)%L

Python N-gram Map

I have developed a data structure in Python to store and query n-grams which is released as open source here. This blog post shall give examples on how to use it.

To add n-grams

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) which map to None

x = NGramMap()
x[('a','a','a')] = None
x[('a','a','b')] = None
x[('a','b','a')] = None
x[('b','a','a')] = None

To count n-gram frequency

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','a','a'), ('a','a','b'), ('a','a','a'), ('a','a','b'), ('a','b','a'), ('b','a','a'), ('a','b','a'), ('b','a','a'), ('a','b','a'), ('a','b','a') ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams():
    print(ngram, x[ngram])

To find n-grams which contain particular elements

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams_with_eles({ 'a', 'y' }):
    print(ngram, x[ngram])

To find n-grams which follow a particular pattern

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams_by_pattern(( None, 'x', 'y' ), { 0 }):
    print(ngram, x[ngram])

To find elements which share similar contexts

You can find elements which occur in the same context in their n-grams, for example 'a' and 'b' share a context in the n-grams (a, x, y) and (b, x, y) as do 'p' and 'q' in the n-grams (x, p, y) and (x, q, y).

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for element in x.elements():
    print(element)
    for ngram in x.ngrams_with_eles({ element }):
        ele_index = ngram.index(element)
        for ngram_ in x.ngrams_by_pattern(ngram, { ele_index }):
            if ngram_[ele_index] != element:
                print("\t", ngram_[ele_index])

Java Trie

After receiving so many visits to my early C# Trie post, I am now releasing source code for a Java Trie, which works in exactly the same way as the C# Trie. The comments have been fixed (I discovered lots of incomplete comments) and some optimizations have been implemented. The code will just be pasted in this post rather than placed in a repository like the C# Trie was. More information can be found in the C# Trie post, but notice that IPrefixMatcher was renamed to PrefixMatcher and PrefixMatcher was renamed to DefaultPrefixMatcher.

Trie class

/*
 * Copyright (c) 2012 Marc Tanti (www.marctanti.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package trie;

/**
 * Trie data structure which maps strings and string prefixes to values.
 * In this implementation, only one PrefixMatcher can be used but it can be modified to use a list of concurrent prefix matchers.
 * @param <V> Type of values to map to.
 */
public class Trie <V> {

    /**
     * The root of the trie.
     */
    private TrieNode<V> root;

    /**
     * PrefixMatcher object for following the prefix of the strings in the trie to their associated values.
     */
    private PrefixMatcher<V> prefixMatcher;

    /**
     * Create an empty trie with an empty root node and an unused prefix matcher.
     */
    public Trie()
    {
        this.root = new TrieNode<V>(null, '\0');
        this.prefixMatcher = new DefaultPrefixMatcher<V>(this.root);
    }

    /**
     * Get the prefix matcher to search for strings with in a character by character basis.
     * @return The prefix matcher. WARNING: There is only one prefix matcher per trie and calling this method will always return the same instance. The instance will retain its previous state.
     */
    public PrefixMatcher<V> getPrefixMatcher() {
        return this.prefixMatcher;
    }

    /**
     * Put a new key-value pair, overwriting the existing value if the given key is already in use.
     * @param key The full string which is associated with the value.
     * @param value The value which is associated with the key.
     */
    public void put(String key, V value)
    {
        TrieNode<V> node = this.root;
        for (char c : key.toCharArray())
        {
            node = node.addChild(c);
        }
        node.setValue(value);
    }

    /**
     * Remove the value that a key leads to and any redundant nodes which result from this deletion.
     * Clears the current matching process.
     * @param key Key of the value to remove.
     */
    public void remove(String key)
    {
        TrieNode<V> node = this.root;
        for (char c : key.toCharArray())
        {
            node = node.getChild(c);
        }
        node.setValue(null);

        //Remove all ancestor nodes which lead to this null value.
        while (node != this.root && !node.isTerminater() && node.numChildren() == 1)
        {
            char prevKey = node.getKey();
            node = node.getParent();
            node.removeChild(prevKey);
        }

        this.prefixMatcher.resetMatch();
    }
    
}

TrieNode class

/*
 * Copyright (c) 2012 Marc Tanti (www.marctanti.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package trie;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Node of the trie.
 * Stores a link to multiple children of type TrieNode, each associated with a key of type Character.
 * If the node terminates a string then it must also store a non-null value of type V.
 * @param <V> The type of the value associated with a complete string.
 */
public class TrieNode <V> {
    
    /**
     * The value stored by this node. If not null then the node terminates a string.
     */
    private V value;
    
    /**
     * The key which is associated with this node, that is, the character that led to this node.
     */
    private char key;
    
    /**
     * The parent of this node.
     */
    private TrieNode<V> parent;
    
    /**
     * The children of this node which can be found through their associated character.
     */
    private HashMap<Character, TrieNode<V>> children;

    /**
     * Create an empty node with no children and null value.
     * @param key The key which is associated with this node, that is, the character that led to this node.
     * @param parent The parent node of this node.
     */
    public TrieNode(TrieNode<V> parent, char key) {
        this.key = key;
        this.parent = parent;
        this.value = null;
        this.children = new HashMap<Character, TrieNode<V>>();
    }

    /**
     * Get the value stored by this node. If the value is not null then the node terminates a string.
     * @return The value stored by this node.
     */
    public V getValue() {
        return value;
    }
    
    /**
     * Set the value stored by this node. If the value is not null then the node terminates a string.
     * @param value The value stored by this node.
     */
    public void setValue(V value) {
        this.value = value;
    }

    /**
     * Get the key which is associated with this node, that is, the character that led to this node.
     * @return The key which is associated with this node.
     */
    public char getKey() {
        return key;
    }

    /**
     * Get the parent of this node.
     * @return The parent of this node.
     */
    public TrieNode<V> getParent() {
        return parent;
    }
    
    /**
     * Get a child of this node which is associated with a key.
     * @param key Key associated with the child of interest.
     * @return The child or null if no child is associated with the given key.
     */
    public TrieNode<V> getChild(char key) {
        if (this.children.containsKey(key)) {
            return this.children.get(key);
        }
        return null;
    }

    /**
     * Check whether or not this node terminates a string and stores a value.
     * @return Whether node stores a value.
     */
    public boolean isTerminater() {
        return this.value != null;
    }

    /**
     * Get the number of children that this node has.
     * @return The number of children.
     */
    public int numChildren() {
        return this.children.size();
    }

    /**
     * Check whether or not this node has any children.
     * @return True if node does not have children, false otherwise.
     */
    public boolean isLeaf() {
        return this.numChildren() == 0;
    }

    /**
     * Check whether or not one of the children of this node is associated with the given key.
     * @param key The key to check for.
     * @return True if a child with given key exists, false otherwise.
     */
    public boolean containsKey(char key) {
        return this.children.containsKey(key);
    }

    /**
     * Add an empty child node (associated with a key) to this node and return the node.
     * @param key The key to associate with the empty child node.
     * @return If the given key already exists then return the existing child node, otherwise return the new child node.
     */
    public TrieNode<V> addChild(char key) {
        if (this.children.containsKey(key)) {
            return this.children.get(key);
        } else {
            TrieNode<V> newChild = new TrieNode<V>(this, key);
            this.children.put(key, newChild);
            return newChild;
        }
    }

    /**
     * Remove the child of a node associated with a key along with all its descendents.
     * @param key The key associated with the child to remove.
     */
    public void removeChild(char key) {
        this.children.remove(key);
    }

    /**
     * Get a list of values contained in this node and all its descendants.
     * Since all the descendants share the same string prefix as this node, then all the values returned will belong to all the strings with this node's prefix.
     * @return A List of values.
     */
    public List<V> prefixMatches() {
        ArrayList<V> values = new ArrayList<V>();
        
        for (TrieNode <V> child : this.children.values()) {
            values.addAll(child.prefixMatches());
        }

        if (this.isTerminater()) {
            values.add(this.value);
        }

        return values;
    }
}

DefaultPrefixMatcher class

/*
 * Copyright (c) 2012 Marc Tanti (www.marctanti.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package trie;

import java.util.List;

/**
 * This class is used to search through a trie for all the strings which have a given prefix. The prefix will be entered character by character.
 * The object from this class is used as a state to mark where the currently entered prefixed has arrived in the trie thus far.
 * This class makes it possible to have a number of matcher objects all concurrently following prefixes in the trie.
 * @param <V> The type of the value associated with a complete string.
 */
public class DefaultPrefixMatcher <V> implements PrefixMatcher<V> {

    /**
     * The root of the trie being searched.
     */
    private TrieNode<V> root;

    /**
     * The trie node that the prefix entered thus far has led to.
     */
    private TrieNode<V> currNode;

    /**
     * The full prefix entered thus far.
     */
    private StringBuffer prefix;
    
    /**
     * Create a matcher, associating it to the trie to search in.
     * @param root Root node of the trie which the matcher will search in.
     */
    public DefaultPrefixMatcher(TrieNode<V> root)
    {
        this.root = root;
        this.currNode = root;
        this.prefix = new StringBuffer();
    }
    
    /**
     * Get the prefix entered so far.
     * @return The prefix entered so far.
     */
    @Override
    public String getPrefix() {
        return this.prefix.toString();
    }

    /**
     * Clear the currently entered prefix.
     */
    @Override
    public void resetMatch() {
        this.currNode = this.root;
        this.prefix = new StringBuffer();
    }
    
    /**
     * Remove the last character of the currently entered prefix.
     */
    @Override
    public void backMatch() {
        if (this.currNode != this.root)
        {
            this.currNode = this.currNode.getParent();
            this.prefix.deleteCharAt(this.prefix.length() - 1);
        }
    }
    
    /**
     * Get the last character of the currently entered prefix.
     * @return The last character of the currently entered prefix.
     */
    @Override
    public char lastMatch() {
        return this.currNode.getKey();
    }
    
    /**
     * Add another character to the end of the prefix if it leads to some existing strings in the trie.
     * If no strings have a matching prefix, character will not be added.
     * @param next Next character in the prefix.
     * @return True if the new prefix was a prefix to some strings in the trie, false otherwise.
     */
    @Override
    public boolean nextMatch(char next) {
        if (this.currNode.containsKey(next))
        {
            this.currNode = this.currNode.getChild(next);
            this.prefix.append(next);
            return true;
        }
        return false;
    }
    
    /**
     * Get all the values associated with strings that share the currently entered prefix.
     * @return The list of values.
     */
    @Override
    public List<V> getPrefixMatches() {
        return this.currNode.prefixMatches();
    }
    
    /**
     * Check if the currently entered prefix is a complete existing string in the trie.
     * @return True if the currently entered prefix is an existing string, false otherwise.
     */
    @Override
    public boolean isExactMatch() {
        return this.currNode.isTerminater();
    }
    
    /**
     * Get the value associate with the complete string that equals the prefix entered thus far.
     * @return The value if the current entered prefix is an existing string, null otherwise.
     */
    @Override
    public V getExactMatch() {
        if (this.isExactMatch()) {
            return this.currNode.getValue();
        }
        return null;
    }
    
}

PrefixMatcher interface

/*
 * Copyright (c) 2012 Marc Tanti (www.marctanti.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package trie;

import java.util.List;

/**
 * A simplified view of the concrete prefix matcher class for the user.
 * This is used to search through a trie for all the strings which have a given prefix. The prefix will be entered character by character.
 * @param <V> The type of the value associated with a complete string.
 */
public interface PrefixMatcher<V> {
    
    /**
     * Get the prefix entered so far.
     * @return The prefix entered so far.
     */
    String getPrefix();
    
    /**
     * Clear the currently entered prefix.
     */
    void resetMatch();
    
    /**
     * Remove the last character of the currently entered prefix.
     */
    void backMatch();
    
    /**
     * Get the last character of the currently entered prefix.
     * @return The last character of the currently entered prefix.
     */
    char lastMatch();
    
    /**
     * Add another character to the end of the prefix if it leads to some existing strings in the trie.
     * If no strings have a matching prefix, character will not be added.
     * @param next Next character in the prefix.
     * @return True if the new prefix was a prefix to some strings in the trie, false otherwise.
     */
    boolean nextMatch(char next);
    
    /**
     * Get all the values associated with strings that share the currently entered prefix.
     * @return The list of values.
     */
    List<V> getPrefixMatches();
    
    /**
     * Check if the currently entered prefix is a complete existing string in the trie.
     * @return True if the currently entered prefix is an existing string, false otherwise.
     */
    boolean isExactMatch();
    
    /**
     * Get the value associate with the complete string that equals the prefix entered thus far.
     * @return The value.
     */
    V getExactMatch();
    
}

Example

//Create trie
Trie<String> trie = new Trie<String>();

//Add some key-value pairs to the trie
trie.put("James", "1");
trie.put("Jake", "2");
trie.put("Fred", "3");

//Search the trie
trie.getPrefixMatcher().nextMatch('J'); //Prefix thus far: "J"
trie.getPrefixMatcher().getPrefixMatches(); //[1, 2]
trie.getPrefixMatcher().isExactMatch(); //false
trie.getPrefixMatcher().nextMatch('a');
trie.getPrefixMatcher().nextMatch('m'); //Prefix thus far: "Jam"
trie.getPrefixMatcher().getPrefixMatches(); //[1]
trie.getPrefixMatcher().nextMatch('e');
trie.getPrefixMatcher().nextMatch('s'); //Prefix thus far: "James"
trie.getPrefixMatcher().isExactMatch(); //true
trie.getPrefixMatcher().getExactMatch(); //1

//Remove a string-value pair
trie.remove("James");

C# Trie

*Update* I have developed a new an improved version of this data structure which you can find here.

For anyone interested, I have also written a Java Trie here.

In a recent project I have ventured into, I had to develop a set of classes in C# for a simple trie which are now released as open source (http://code.google.com/p/typocalypse/source/browse/#hg/Trie). This blog post shall describe how it works and how to use it.

Introduction to tries

Simple tries are a data structure for mapping strings to values such that it enables you to efficiently retrieve all the values whose key strings have a particular prefix. This works by storing all the strings in a tree where each node is a prefix to a number of strings and each edge is a character to append to the prefix in the parent node. The root node is the empty string which is a prefix to all strings.

As you traverse a path from the root downwards, you follow the edges which lead to prefixes of the string you are trying to match. Eventually if such a string exists, a node will be pointing to the value mapped by the string. By traversing the descendants of a particular node, you can retrieve all the stored strings which have that prefix in common and their corresponding value.

Here's a diagram example from wikipedia:
http://upload.wikimedia.org/wikipedia/commons/b/be/Trie_example.svg

Implemented trie

The implemented trie supports adding, removing and character-by-character prefix searching of string-value pairs.

The way it works is by keeping a reference in each node to a value object such that if the reference is null then the node does not point to a value object and hence the prefix is not a complete string. The type of the values is generic, any referencable type is allowed. Each node points to its children via a Dictionary object which maps characters to nodes, thereby allowing a fast search by following the characters.

The following is a description of each class:

TrieNode

This is a non-public class which represents the nodes of the trie, that is, the prefixes. However in this implementation, the prefix itself is not stored, only the last character of the prefix called the Key is stored in order to know which character was followed to access this node. It also stores the value (generic type), a pointer to the parent node and a dictionary which maps characters to children nodes. If this node terminates a string then it's value field points to an object, otherwise it is null.

PrefixMatcher

This is a non-public class which is dedicated to allow the user to search the trie for a particular string or strings with a particular prefix. It was designed for enabling the user to search for the values of said strings on a character by character basis rather than providing the whole string immediately so that it can be used to search for user input as the user types in the query. This requires the maintenance of a state so that it is known which prefix has been entered thus far as well as which node that prefix is found in so as to enable an efficient search. For this reason the search feature was kept in a class of its own. Each time the trie is modified with the removal of a string, the current search is cancelled and must be redone from first character so as to avoid the user from searching non-existent strings.

IPrefixMatcher

This is a public interface which abstracts the methods of the PrefixMatcher class so that the user is provided with an abstraction rather than a concrete class in order to search.

Trie

This is the main class which provides the features of the trie data structure. Searching is done through the public property "Matcher" which returns an instance of IPrefixMatcher. When a string is removed, the current search is cleared so as to avoid the user from searching non-existent strings.

Examples

Here is an example of how to use the implemented trie:

//Create trie
Trie < string > trie = new Trie < string > ();

//Add some key-value pairs to the trie
trie.Put("James", "112");
trie.Put("Jake", "222");
trie.Put("Fred", "326");

//Search the trie
trie.Matcher.NextMatch('J'); //Prefix thus far: "J"
trie.Matcher.GetPrefixMatches(); //[112, 222]
trie.Matcher.IsExactMatch(); //false
trie.Matcher.NextMatch('a');
trie.Matcher.NextMatch('m'); //Prefix thus far: "Jam"
trie.Matcher.GetPrefixMatches(); //[112]
trie.Matcher.NextMatch('e');
trie.Matcher.NextMatch('s'); //Prefix thus far: "James"
trie.Matcher.IsExactMatch(); //true
trie.Matcher.GetExactMatch(); //112

//Remove a string-value pair
trie.Remove("James");

Link to classes

http://code.google.com/p/typocalypse/source/browse/#hg/Trie