Java Trie优化

Question

我一直trie在练习数据结构（与课程工作无关）。此类用于存储字符串的子字符串。对于长度的串n有n(n+1)/2总的子串。特别地，这种trie保留方式的实现保留了自然顺序，并且比TreeMap或TreeSet对随机字符串更有效。同样，存储单个字符而不是整个字符串可以节省内存。

我认为对于存储子字符串而言，后缀数组可能是更好的方法，但我想确保在开始新项目之前已针对速度合理地优化了这个trie类。

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();
    }
}

Answer 1

请参阅上面的评论，但无论如何要注意以下几点：

您立即分配26个子尝试，无论是否使用它们。您可以懒惰地创建这些（即，仅当遇到特定字母时）。

您的代码仅适用于纯ASCII字母，不能处理外来字符，连字符，撇号或大小写混合的字符。延迟分配也将对此有所帮助。

您的实现每个使用Trie对象char，再加上一些空的备用组件，因此可能会占用大量内存。

这可能是更好的收集结果在getString()正确的顺序，而不是追加，然后倒车，但你需要这个基准。如果跟踪Trie的深度，则可以分配正确长度的数组，而不是StringBuilder-但是跟踪深度有其自身的内存成本。