Suffix tree: Difference between revisions
bugfix, and include visualization
(J: partial bugfix) |
(bugfix, and include visualization) |
||
Line 134:
tree=. root
for_box.classify y do.
char=. {.>{.>box
subtree=. }.build_tree }.each>box
ndx=.I.0=1&{::"1 subtree
n=.#tree
if. 1=#ndx do.
counts=. 1 + 0&{::"1 subtree
parents=. (
edges=. (ndx}~ <@(char,ndx&{::)) 2&{"1 subtree
else.
tree=. tree,(__;0;,char),(1;n;0) + ::]&.>"1 subtree
end.
end.
)
Line 157:
Task example:
<lang J>
┌──┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│__│1 │_│_ │2 │4│6│_ │3 │5│7│
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│_ │0 │0│2
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
Line 171:
The third row is the edge's substring (empty for root node).
Visualizing, using [[Visualize_a_tree#J|showtree]] and prefixing the substring leading to each leaf with the leaf number (in brackets):
<lang J>fmttree=: (;@(1&{) showtree~ {: (,~ }.`('[','] ',~":)@.(_>|))each {.)
fmttree suffix_tree 'banana$'
┌─ [1] banana$
│ ┌─ [2] na$
│ ┌─ na ────┴─ [4] $
────┼─ a ─────────┴─ [6] $
│ ┌─ [3] na$
├─ na ────────┴─ [5] $
└─ [7] $
</lang>
=={{header|Perl}}==
| |||