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字母，并且不处理外来字符，连字符，撇号或混合大小写。懒惰的分配也会对此有所帮助。

您的实现使用每个char的Trie对象以及一些空的备用，所以可能会占用很大的内存。

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