Java Trie Optimization

Question

I have been toying with a trie data structure for practice (there is not course work related). This class is used to store substrings of a string. For a string of length n there are n(n+1)/2 total substrings. In particular this implementation of a trie preserves natural ordering and is more efficient than a TreeMap or TreeSet on random strings. As well storing a single character rather than the entire string saves on memory.

I think for storing substrings a suffix array may be the better way to go but I wanted to make sure this trie class is reasonably optimized for speed before starting a new project.

class Trie
{
    final Trie my_parent;
    final Trie[] my_children;
    final char my_value;

    public Trie(final Trie the_parent, final char the_value)
    {
        my_parent = the_parent;
        my_value = the_value;
        my_children = new Trie[26];
    }

    public int insertIterative(final char[] the_text)
    {
        int number = 0;
        Trie parent = this;

        for(int ator = 0; ator < the_text.length; ator++)
        {
            final int key = the_text[ator] - 97;
            Trie child = parent.my_children[key];

            if(child == null)
            {
                child =  new Trie(parent, the_text[ator]);
                parent.my_children[key] = child;
                number++;
            }

            parent = child;
        }   

        return number;
    }

    public String getString()
    {
        final StringBuilder builder = new StringBuilder();
        Trie parent = this;

        while(parent.my_parent != null)
        {
            builder.append(parent.my_value);
            parent = parent.my_parent;
        }

        return builder.reverse().toString();
    }
}

Have you noticed any particular performance problem that you want help with? How about running your code through a profiler to see which parts take the most time? When you say "optimize" do you mean speed or memory? — DNA, Feb 29 '12 at 09:03
It is hard to say in the terms of speed as I have nothing to compare against. I have never heard of a profiler will have to take a look at that. — ntin, Feb 29 '12 at 09:23
You could compare against other Trie implementations - see this question, for example: http://stackoverflow.com/questions/623892/where-do-i-find-a-standard-trie-based-map-implementation-in-java or this: http://stackoverflow.com/questions/3806788/trie-data-structures-java — DNA, Feb 29 '12 at 15:25

DNA · Answer 1 · 2012-02-29T09:13:19.017

See my comment above, but a few observations anyway:

You allocate 26 child Tries immediately, regardless of whether they are used. You could create these lazily (i.e. only when you encounter a particular letter).

Your code will only work for plain ASCII letters, and doesn't handle foreign characters, hyphens, apostrophes or mixed case. Lazy allocation would also help with this.

Your implementation uses a Trie object per char, plus some empty spares, so is likely to be quite heavy on memory usage.

It might be better to collect the result in getString() in the correct order rather than appending and then reversing, but you'd need to benchmark this. If you kept track of the depth of the Trie, then you could allocate an array of the correct length, rather than a StringBuilder - but tracking the depth has its own memory cost.

I never actually considered but an empty array still needs to allocated memory for null pointers which would be 4 bytes (32bit) or 8 bytes (64bit). If the Trie has a 100,000 nodes that adds up to a fair amount of wasted storage. — ntin, Feb 29 '12 at 09:52

Java Trie Optimization

1 Answers1