Suffix tree: Difference between revisions

2,674 bytes added ,  27 days ago
m
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible)
 
(3 intermediate revisions by 3 users not shown)
Line 23:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">T Node
String sub
[Int] ch
Line 73:
R
 
F f(Int n, String pre) -> NVoid
V children = @.nodes[n].ch
I children.empty
Line 86:
f(0, ‘’)
 
SuffixTree(‘banana$’).visualize()</langsyntaxhighlight>
 
{{out}}
Line 105:
=={{header|C sharp|C#}}==
{{trans|C++}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
 
Line 214:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>+
Line 230:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <functional>
#include <iostream>
#include <vector>
Line 334:
int main() {
SuffixTree("banana$").visualize();
}</langsyntaxhighlight>
{{out}}
<pre>+
Line 350:
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.stdio;
 
struct Node {
Line 442:
void main() {
SuffixTree("banana$").visualize();
}</langsyntaxhighlight>
{{out}}
<pre>┐
Line 455:
│ └─╴ $
└─╴ $</pre>
 
== Elixir ==
<syntaxhighlight lang="elixir">defmodule STree do
defstruct branch: []
defp suffixes([]), do: []
defp suffixes(w), do: [w | suffixes tl(w)]
defp lcp([], _, acc), do: acc
defp lcp(_, [], acc), do: acc
defp lcp([c | u], [a | w], acc) do
if c == a do
lcp(u, w, acc + 1)
else acc
end
end
defp g([], aw), do: [{{aw, length aw}, nil}]
defp g(cusnes, aw) do
[cusn | es] = cusnes
{cus, node} = cusn
{cu, culen} = cus
cpl = case node do
nil -> lcp cu, aw, 0
_ -> lcp (Enum.take cu, culen), aw, 0
end
x = Enum.drop cu, cpl
xlen = culen - cpl
y = Enum.drop aw, cpl
ex = {{x, xlen}, node}
ey = {{y, length y}, nil}
cond do
hd(aw) > hd(cu) -> [cusn | g(es, aw)]
hd(aw) < hd(cu) -> [{{aw, length aw}, nil} | cusnes]
nil != node && xlen == 0 -> [{cus, insert_suffix(y, node)} | es]
hd(x) < hd(y) -> [{{cu, cpl}, %STree{branch: [ex, ey]}} | es]
true -> [{{cu, cpl}, %STree{branch: [ey, ex]}} | es]
end
end
 
defp insert_suffix(aw, node), do: %STree{branch: g(node.branch, aw)}
def naive_insertion(t), do: List.foldl(suffixes(t), %STree{}, &insert_suffix/2)
 
defp f(nil, _, label), do: IO.puts("╴ #{label}")
defp f(%STree{branch: children}, pre, label) do
IO.puts "┐ #{label}"
children
|> Enum.take(length(children) - 1)
|> Enum.each(fn c ->
IO.write(pre <> "├─")
{ws, len} = elem(c, 0)
f(elem(c, 1), pre <> "│ ", Enum.join(Enum.take ws, len))
end)
IO.write(pre <> "└─")
c = List.last(children)
{ws, len} = elem(c, 0)
f(elem(c, 1), pre <> " ", Enum.join(Enum.take ws, len))
end
 
def visualize(n), do: f(n, "", "")
 
def main do
"banana$"
|> String.graphemes
|> naive_insertion
|> visualize
end
end</syntaxhighlight>
 
{{out}}
<pre>
├─╴ $
├─┐ a
│ ├─╴ $
│ └─┐ na
│ ├─╴ $
│ └─╴ na$
├─╴ banana$
└─┐ na
├─╴ $
└─╴ na$
</langpre>
 
=={{header|Go}}==
Vis function from [[Visualize_a_tree#Unicode]].
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 543 ⟶ 627:
}
f(0, "")
}</langsyntaxhighlight>
{{out}}
<pre>
Line 563 ⟶ 647:
Implementation:
 
<langsyntaxhighlight Jlang="j">classify=: {.@> </. ]
 
build_tree=:3 :0
Line 589 ⟶ 673:
tree=. B=:|:build_tree <\. y
((1+#y)-each {.tree),}.tree
)</langsyntaxhighlight>
 
Task example:
 
<langsyntaxhighlight Jlang="j"> suffix_tree 'banana$'
┌──┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│__│1 │_│_ │2 │4│6│_ │3 │5│7│
Line 600 ⟶ 684:
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
└──┴───────┴─┴──┴───┴─┴─┴──┴───┴─┴─┘</langsyntaxhighlight>
 
The first row is the leaf number (_ for internal nodes).
Line 610 ⟶ 694:
Visualizing, using [[Visualize_a_tree#J|showtree]] and prefixing the substring leading to each leaf with the leaf number (in brackets):
 
<langsyntaxhighlight Jlang="j">fmttree=: ;@(1&{) showtree~ {: (,~ }.`('[','] ',~":)@.(_>|))each {.
 
fmttree suffix_tree 'banana$'
Line 620 ⟶ 704:
├─ na ────────┴─ [5] $
└─ [7] $
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.util.ArrayList;
import java.util.List;
 
Line 717 ⟶ 801:
new SuffixTree("banana$").visualize();
}
}</langsyntaxhighlight>
{{out}}
<pre>┐
Line 733 ⟶ 817:
=={{header|JavaScript}}==
{{trans|Java}}
<langsyntaxhighlight JavaScriptlang="javascript">class Node {
sub = ''; // a substring of the input string
children = []; // list of child nodes
Line 819 ⟶ 903:
 
const st = new SuffixTree('banana');
console.log(st.toString());</langsyntaxhighlight>
 
{{out}}
Line 834 ⟶ 918:
=={{header|Julia}}==
{{trans|Go}}
<langsyntaxhighlight lang="julia">import Base.print
 
mutable struct Node
Line 907 ⟶ 991:
 
println(SuffixTree("banana\$"))
</langsyntaxhighlight> {{out}}
<pre>
Line 924 ⟶ 1,008:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
class Node {
Line 1,009 ⟶ 1,093:
fun main(args: Array<String>) {
SuffixTree("banana$").visualize()
}</langsyntaxhighlight>
 
{{out}}
Line 1,028 ⟶ 1,112:
=={{header|Nim}}==
{{trans|Go}}
<langsyntaxhighlight Nimlang="nim">type
 
Tree = seq[Node]
Line 1,098 ⟶ 1,182:
 
 
newTree("banana$").vis()</langsyntaxhighlight>
 
{{out}}
Line 1,115 ⟶ 1,199:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight Perllang="perl">use strict;
use warnings;
use Data::Dumper;
Line 1,145 ⟶ 1,229:
return $h;
}
print +Dumper suffix_tree suffixes 'banana$';</langsyntaxhighlight>
{{out}}
<pre>$VAR1 = {
Line 1,165 ⟶ 1,249:
=={{header|Phix}}==
{{trans|D}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- tree nodes are simply {string substr, sequence children_idx}</span>
Line 1,238 ⟶ 1,322:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SuffixTree</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"banana$"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">visualize</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,256 ⟶ 1,340:
=={{header|Python}}==
{{trans|D}}
<langsyntaxhighlight lang="python">class Node:
def __init__(self, sub="", children=None):
self.sub = sub
Line 1,322 ⟶ 1,406:
f(0, "")
 
SuffixTree("banana$").visualize()</langsyntaxhighlight>
{{out}}
<pre>+-
Line 1,340 ⟶ 1,424:
by Danny Yoo for more information on how to use suffix trees in Racket.
 
<langsyntaxhighlight lang="racket">#lang racket
(require (planet dyoo/suffixtree))
(define tree (make-tree))
Line 1,356 ⟶ 1,440:
((list c ct ...) (show-node c (string-append dpth " |")) (l ct)))))
 
(show-node (tree-root tree) "")</langsyntaxhighlight>
 
{{out}}
Line 1,378 ⟶ 1,462:
The display code is a variant of the [[visualize_a_tree#Raku|visualize a tree]] task code.
 
<syntaxhighlight lang="raku" perl6line>multi suffix-tree(Str $str) { suffix-tree flat map &flip, [\~] $str.flip.comb }
multi suffix-tree(@a) {
hash
Line 1,415 ⟶ 1,499:
}
flat visit($tree, $indent xx 2);
}</langsyntaxhighlight>
 
{{out}}
Line 1,432 ⟶ 1,516:
=={{header|Sidef}}==
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">func suffix_tree(Str t) {
suffix_tree(^t.len -> map { t.substr(_) })
}
Line 1,456 ⟶ 1,540:
}
 
say suffix_tree('banana$')</langsyntaxhighlight>
{{out}}
<pre>
Line 1,478 ⟶ 1,562:
=={{header|Wren}}==
{{trans|Kotlin}}
<langsyntaxhighlight ecmascriptlang="wren">class Node {
construct new() {
_sub = "" // a substring of the input string
Line 1,568 ⟶ 1,652:
}
 
SuffixTree.new("banana$").visualize()</langsyntaxhighlight>
 
{{out}}
1,480

edits