天真的后缀树在Java中的实现

Question

我想用O（m^2）而不是Ukkonen写一个天真的建筑算法来编写后缀树类。

我的疑问是关于如何表示树。到目前为止，我已经得到了这个。但我不认为这是节点和边的写类结构。任何有关如何保持节点和边缘之间的映射/关系的建议。重要的一点是，在边缘我们只是存储开始和结束索引以节省空间。

class suffixTree{ 
Node[] nodes; 
Edge[] edge; 
} 

class Node{ 
    int node_id; 
    Edge[] outgoingEdges; 
} 

class Edge{ 
    int start_index; 
    int end_index; 
    int start_node_id; 
    int end_node_id; 
} 

Answer 1

我会做这种方式：

class SuffixTree { 
    // A tree only needs to know about the root Node. 
    Node root; 
} 

// A Node contains a mapping from the first character to 
// an Edge that corresponds to it. 
// It doesn't need to know about anything else. 
class Node { 
    Map<Character, Edge> edgeMap; 
} 

// An Edge contains only the start and the end index of the substring 
// and the destination Node. 
class Edge { 
    int startIndex; 
    int endIndex; 
    Node destination; 
} 

最重要的变化是：

1. 入门在所有三类去掉冗余信息。

2. 使用引用而不是数组和索引。