Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

201
LINES

< > BotCompany Repo | #1029221 // SuffixTree [backup, optimizing away the position field, works]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (14900L/101K).

1  
// A naive suffix tree implementation
2  
sclass SuffixTree {
3  
  Node root;
4  
  S fullText;
5  
  int nodeCount;
6  
  
7  
  Comparator<IFirstChar> childComparator = (a, b) -> a.firstCharOrMinus1(this)-b.firstCharOrMinus1(this);
8  
  new DummyNode dummyNode;
9  
  
10  
  sinterface IFirstChar {
11  
    int firstCharOrMinus1(SuffixTree tree);
12  
  }
13  
  
14  
  sclass DummyNode implements IFirstChar {
15  
    int firstChar;
16  
    
17  
    public int firstCharOrMinus1(SuffixTree tree) { ret firstChar; }
18  
  }
19  
20  
  sclass Node implements IFirstChar {
21  
    int from, to; // our range in fullText
22  
    O children; // null, a Node or Node[] sorted by first character
23  
24  
    *() {}
25  
    *(int *from, int *to) {}
26  
    *(Substring s) { from = s.startIndex(); to = s.endIndex(); }
27  
    
28  
    Substring text(SuffixTree tree) { ret Substring(tree.fullText, from, to); }
29  
    
30  
    int lText() { ret to-from; }
31  
    
32  
    bool isTerminal(SuffixTree tree) { ret to == l(tree.fullText); }
33  
    
34  
    void addChild(SuffixTree tree, Node n) {
35  
      if (children == null) children = n;
36  
      else if (children cast Node)
37  
        children = sortArrayInPlace(new Node[] {children, n}, tree.childComparator);
38  
      else {
39  
        Node[] c = cast children;
40  
        Node[] x = new[l(c)+1];
41  
        arraycopy(c, 0, x, 0, l(c));
42  
        x[l(x)-1] = n;
43  
        children = sortArrayInPlace(x, tree.childComparator);
44  
      }
45  
    }
46  
    
47  
    Cl<Node> children() {
48  
      if (children == null) ret emptyList();
49  
      if (children cast Node) ret ll(children);
50  
      ret wrapArrayAsList((Node[]) children);
51  
    }
52  
    
53  
    CompactTreeSet<IFirstChar> makeEmptyChildrenSet(SuffixTree tree) { ret new CompactTreeSet<>(tree.childComparator); }
54  
    
55  
    public int firstCharOrMinus1(SuffixTree tree) {
56  
      ret charToIntOrMinus1(text(tree));
57  
    }
58  
    
59  
    Node getChild(SuffixTree tree, int c) {
60  
      if (children == null) null;
61  
      if (children cast Node)
62  
        ret children.firstCharOrMinus1(tree) == c ? children : null;
63  
      tree.dummyNode.firstChar = c;
64  
      Node[] x = cast children;
65  
      int i = Arrays.binarySearch(x, tree.dummyNode, tree.childComparator);
66  
      ret i >= 0 ? x[i] : null;
67  
    }
68  
  }
69  
70  
  *() {}
71  
  *(S *fullText) {
72  
    root = new Node(0, 0);
73  
    ++nodeCount;
74  
    for i over fullText: {
75  
      addSuffix(Substring(fullText, i));
76  
      if (((i+1) % 1000000) == 0)
77  
        print((i+1) + " suffixes added (" + nNodes(nodeCount) + ")");
78  
    }
79  
  }
80  
81  
  void addSuffix(Substring s) {
82  
    Node node = root;
83  
    
84  
    while (!empty(s)) {
85  
      int _n = lCommonPrefix_CharSequence(node.text(SuffixTree.this), s);
86  
      s = s.substring(_n);
87  
      if (_n >= node.lText()) { // node text exhausted
88  
        if (empty(s)) { // pattern also exhausted - done
89  
          //print("Exhausted: " + node.from + "/" + node.to);
90  
          // add a new termination node
91  
          Node nNew = new Node(s);
92  
          ++nodeCount;
93  
          node.addChild(SuffixTree.this, nNew);
94  
          ret;
95  
        } else {
96  
          Node n = node.getChild(SuffixTree.this, charToIntOrMinus1(s));
97  
          if (n == null) {
98  
            n = new Node(s);
99  
            ++nodeCount;
100  
            node.addChild(SuffixTree.this, n);
101  
            ret;
102  
          } else
103  
            node = n;
104  
        }
105  
      } else { // node text not exhausted
106  
        // split node. first, move all the node's vitals to a new node nOld
107  
        Node nOld = new Node(node.from+_n, node.to);
108  
        ++nodeCount;
109  
        nOld.children = node.children;
110  
        node.children = null;
111  
        node.to = node.from+_n;
112  
        node.addChild(SuffixTree.this, nOld);
113  
114  
        // now add a new node
115  
        Node nNew = new Node(s);
116  
        ++nodeCount;
117  
        node.addChild(SuffixTree.this, nNew);
118  
        ret;
119  
      }
120  
    }
121  
  }
122  
123  
  public L<Int> indicesOf(S pattern) {
124  
    ret asList(indicesOf_iterator(pattern));
125  
  }
126  
127  
  public ItIt<Int> indicesOf_iterator(S pattern) {
128  
    ret mapI_notNull(allNodesUnder(scanDown(root, pattern)),
129  
      nad -> nad.node.isTerminal(this) ? nad.position() : null);
130  
  }
131  
  
132  
  srecord NodeAndDepth(Node node, int depth) {
133  
    int position() {
134  
      int position = node.from-depth;
135  
      //print("from=" + node.from + ", to=" + node.to + ", depth=" + depth + ", position=" + position);
136  
      ret position;
137  
    }
138  
    
139  
    Cl<NodeAndDepth> children() {
140  
      ret lmap wrapChild(node.children());
141  
    }
142  
    
143  
    NodeAndDepth wrapChild(Node n) {
144  
      ret n == null ? null : new NodeAndDepth(n, depth+node.lText());
145  
    }
146  
    
147  
    NodeAndDepth getChild(SuffixTree tree, int c) {
148  
      ret wrapChild(node.getChild(tree, c));
149  
    }
150  
  }
151  
152  
  NodeAndDepth scanDown(Node node, S pattern) {
153  
    int lPattern = l(pattern), iPattern = 0;
154  
    NodeAndDepth nad = new(node, 0);
155  
    while true {
156  
      int n = lCommonPrefix_CharSequence(nad.node.text(this), Substring(pattern, iPattern));
157  
      iPattern += n;
158  
      if (iPattern >= lPattern) break; // pattern exhausted - done
159  
      if (n < nad.node.lText()) null; // mismatch, exit
160  
      NodeAndDepth child = nad.getChild(SuffixTree.this, charAtAsIntOrMinus1(pattern, iPattern));
161  
      if (child != null) continue with nad = child;
162  
      null;
163  
    }
164  
    
165  
    ret nad;
166  
  }
167  
  
168  
  void printMe() {
169  
    printNode("", "", new NodeAndDepth(root, 0));
170  
  }
171  
  
172  
  void printNode(S indent, S pre, NodeAndDepth nad) {
173  
    print(indent + pre + quote(shorten(20, nad.node.text(this))) + (!nad.node.isTerminal(this) ? "" : " [" + nad.position() + "]"));
174  
    fOr (NodeAndDepth n : nad.children()) {
175  
      printNode(indent + "  ", "[" + (n.node.lText() == 0 ? "end" : quote(n.node.text(this).charAt(0))) + "] ", n);
176  
    }
177  
  }
178  
  
179  
  ItIt<NodeAndDepth> allNodes() {
180  
    ret allNodesUnder(new NodeAndDepth(root, 0));
181  
  }
182  
  
183  
  // includes the node itself
184  
  ItIt<NodeAndDepth> allNodesUnder(NodeAndDepth nad) {
185  
    new L<Iterator<NodeAndDepth>> stack;
186  
    if (nad != null)
187  
      stack.add(iteratorLL(nad));
188  
    ret iteratorFromFunction_if0(() -> {
189  
      while (nempty(stack)) {
190  
        if (!last(stack).hasNext())
191  
          popLast(stack);
192  
        else {
193  
          NodeAndDepth n = last(stack).next();
194  
          stack.add((Iterator) iterator(n.children()));
195  
          ret n;
196  
        }
197  
      }
198  
      null;
199  
    });
200  
  }
201  
}

Author comment

Began life as a copy of #1029202

download  show line numbers  debug dex  old transpilations   

Travelled to 7 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt, xrpafgyirdlv

No comments. add comment

Snippet ID: #1029221
Snippet name: SuffixTree [backup, optimizing away the position field, works]
Eternal ID of this version: #1029221/22
Text MD5: 0edd3b0bf8ce958d518adfb53ef6969f
Transpilation MD5: 576b99c627738db1fdb1c9ab72a3257f
Author: stefan
Category: javax / text searching
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2020-07-26 02:37:20
Source code size: 6297 bytes / 201 lines
Pitched / IR pitched: No / No
Views / Downloads: 208 / 355
Version history: 21 change(s)
Referenced in: [show references]