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

171
LINES

< > BotCompany Repo | #1029215 // SuffixTree [another optimized backup]

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

Libraryless. Click here for Pure Java version (14689L/100K).

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  
    CompactTreeSet<IFirstChar> children; // actually, <Node>
23  
    int position = -1;
24  
25  
    *() {}
26  
    *(int *from, int *to) {}
27  
    *(Substring s) { from = s.startIndex(); to = s.endIndex(); }
28  
    
29  
    Substring text(SuffixTree tree) { ret Substring(tree.fullText, from, to); }
30  
    
31  
    int lText() { ret to-from; }
32  
    
33  
    void addPosition(int i) {
34  
      if (position >= 0) fail("Already have position");
35  
      position = i;
36  
    }
37  
    
38  
    void addChild(SuffixTree tree, Node n) {
39  
      if (children == null) children = makeEmptyChildrenSet(tree);
40  
      children.add(n);
41  
    }
42  
    
43  
    CompactTreeSet<IFirstChar> makeEmptyChildrenSet(SuffixTree tree) { ret new CompactTreeSet<>(tree.childComparator); }
44  
    
45  
    public int firstCharOrMinus1(SuffixTree tree) {
46  
      ret charToIntOrMinus1(text(tree));
47  
    }
48  
    
49  
    Node getChild(SuffixTree tree, int c) {
50  
      if (children == null) null;
51  
      tree.dummyNode.firstChar = c;
52  
      ret (Node) children.find(tree.dummyNode);
53  
    }
54  
  }
55  
56  
  *() {}
57  
  *(S *fullText) {
58  
    root = new Node(0, 0);
59  
    ++nodeCount;
60  
    for i over fullText: {
61  
      addSuffix(Substring(fullText, i), i);
62  
      if (((i+1) % 1000000) == 0)
63  
        print((i+1) + " suffixes added (" + nNodes(nodeCount) + ")");
64  
    }
65  
  }
66  
67  
  void addSuffix(Substring s, int position) {
68  
    Node node = root;
69  
    
70  
    while (!empty(s)) {
71  
      int _n = lCommonPrefix_CharSequence(node.text(SuffixTree.this), s);
72  
      s = s.substring(_n);
73  
      if (_n >= node.lText()) { // node text exhausted
74  
        if (empty(s)) { // pattern also exhausted - done
75  
          node.addPosition(position);
76  
          ret;
77  
        } else {
78  
          Node n = node.getChild(SuffixTree.this, charToIntOrMinus1(s));
79  
          if (n == null) {
80  
            n = new Node(s);
81  
            ++nodeCount;
82  
            n.addPosition(position);
83  
            node.addChild(SuffixTree.this, n);
84  
            ret;
85  
          } else
86  
            node = n;
87  
        }
88  
      } else { // node text not exhausted
89  
        // split node. first, move all the node's vitals to a new node nOld
90  
        Node nOld = new Node(node.from+_n, node.to);
91  
        ++nodeCount;
92  
        nOld.position = node.position;
93  
        node.position = -1;
94  
        nOld.children = node.children;
95  
        node.children = null;
96  
        node.to = node.from+_n;
97  
        node.addChild(SuffixTree.this, nOld);
98  
99  
        // now add a new node
100  
        Node nNew = new Node(s);
101  
        ++nodeCount;
102  
        nNew.addPosition(position);
103  
        node.addChild(SuffixTree.this, nNew);
104  
        ret;
105  
      }
106  
    }
107  
  }
108  
109  
  public L<Int> indicesOf(S pattern) {
110  
    new IntBuffer out;
111  
    getIndicesOf(out, root, pattern, 0);
112  
    ret out.asVirtualList();
113  
  }
114  
  
115  
  void getIndicesOf(IntBuffer out, Node node, S pattern, int iPattern) {
116  
    int lPattern = l(pattern);
117  
    while true {
118  
      int n = lCommonPrefix_CharSequence(node.text(this), Substring(pattern, iPattern));
119  
      iPattern += n;
120  
      if (iPattern >= lPattern) break; // pattern exhausted - done
121  
      if (n < node.lText()) ret; // mismatch, exit
122  
      Node child = node.getChild(SuffixTree.this, charAtAsIntOrMinus1(pattern, iPattern));
123  
      if (child != null) continue with node = child;
124  
      ret;
125  
    }
126  
    
127  
    collectPositions(out, node);
128  
  }
129  
  
130  
  L<Int> getPositions(Node node) {
131  
    new IntBuffer out;
132  
    collectPositions(out, node);
133  
    ret out.asVirtualList();
134  
  }
135  
  
136  
  void collectPositions(IntBuffer out, Node node) {
137  
    if (node == null) ret;
138  
    if (node.position >= 0) out.add(node.position);
139  
    fOr (IFirstChar n : node.children)
140  
      collectPositions(out, (Node) n);
141  
  }
142  
  
143  
  void printMe() {
144  
    printNode("", "", root);
145  
  }
146  
  
147  
  void printNode(S indent, S pre, Node node) {
148  
    print(indent + pre + quote(shorten(20, node.text(this))) + (node.position < 0 ? "" : " [" + node.position + "]"));
149  
    fOr (IFirstChar _n : node.children) {
150  
      Node n = cast _n;
151  
      printNode(indent + "  ", "[" + (n.lText() == 0 ? "end" : quote(n.text(this).charAt(0))) + "] ", n);
152  
    }
153  
  }
154  
  
155  
  ItIt<Node> allNodes() {
156  
    new L<Iterator<Node>> stack;
157  
    stack.add(iteratorLL(root));
158  
    ret iteratorFromFunction_if0(() -> {
159  
      while (nempty(stack)) {
160  
        if (!last(stack).hasNext())
161  
          popLast(stack);
162  
        else {
163  
          Node n = last(stack).next();
164  
          stack.add((Iterator) iterator(n.children));
165  
          ret n;
166  
        }
167  
      }
168  
      null;
169  
    });
170  
  }
171  
}

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: #1029215
Snippet name: SuffixTree [another optimized backup]
Eternal ID of this version: #1029215/1
Text MD5: ceb6bc478b58ff5ea43505d73031fa24
Transpilation MD5: b6b9de0cb0b06c587acbf5284c34efbd
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-25 14:39:56
Source code size: 5077 bytes / 171 lines
Pitched / IR pitched: No / No
Views / Downloads: 168 / 232
Referenced in: [show references]