Java Trie 优化

Question

我一直在练习 trie 数据结构(与类(class)作业无关)。此类用于存储字符串的子字符串。对于长度为 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 个子 Tries，不管它们是否被使用。您可以延迟创建这些(即仅当您遇到特定字母时)。

您的代码仅适用于纯 ASCII 字母，不处理外来字符、连字符、撇号或混合大小写。惰性分配也有助于此。

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

可能以正确的顺序在 getString() 中收集结果比附加然后反转更好，但您需要对此进行基准测试。如果您跟踪 Trie 的深度，那么您可以分配一个长度正确的数组，而不是 StringBuilder - 但跟踪深度有其自身的内存成本。