Suffix tree: Difference between revisions
m →{{header|Perl}}: updating output as well |
update task description. |
||
Line 1: | Line 1: | ||
{{draft task}} |
{{draft task}} |
||
A [[wp:suffix tree|suffix tree]] is a data structure commonly used in [[wp:string algorithms|string algorithms]] |
A [[wp:suffix tree|suffix tree]] is a data structure commonly used in [[wp:string algorithms|string algorithms]]. |
||
Given a string S of length n, its suffix tree is a tree T such that: |
|||
<!-- TODO: more detailed explanation, + maybe a graphical example --> |
|||
* T has exactly n leaves numbered from 1 to n. |
|||
For this task, build the suffix tree of the string "banana$", and show that its edges are: |
|||
* Except for the root, every internal node has at least two children. |
|||
* Each edge of T is labelled with a non-empty substring of S. |
|||
* No two edges starting out of a node can have string labels beginning with the same character. |
|||
* The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n. |
|||
Such a tree does not exist for any string. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose. |
|||
<pre>$ $ $ $ a banana$ na na na$ na$</pre> |
|||
For this task, build and display the suffix tree of the string "banana$". Displaying the tree can be done using the code from the [[visualize a tree]] task, but any other convenient method is accepted. |
|||
There are several ways to implement the tree data structure, for instance how edges labels should be encoded. Latitude is given in this matter. |
|||
Extra-credit: use the [[visualize a tree]] task in order to show the whole tree. |
|||
The computation time for an efficient algorithm should be <math>O(n)</math>, but such an algorithm might be difficult to implement. An easier, <math>O(n^2)</math> algorithm is accepted. |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 17:33, 26 August 2013
A suffix tree is a data structure commonly used in string algorithms.
Given a string S of length n, its suffix tree is a tree T such that:
- T has exactly n leaves numbered from 1 to n.
- Except for the root, every internal node has at least two children.
- Each edge of T is labelled with a non-empty substring of S.
- No two edges starting out of a node can have string labels beginning with the same character.
- The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n.
Such a tree does not exist for any string. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose.
For this task, build and display the suffix tree of the string "banana$". Displaying the tree can be done using the code from the visualize a tree task, but any other convenient method is accepted.
There are several ways to implement the tree data structure, for instance how edges labels should be encoded. Latitude is given in this matter.
The computation time for an efficient algorithm should be , but such an algorithm might be difficult to implement. An easier, algorithm is accepted.
Perl
<lang Perl>use strict; use warnings; use Data::Dumper;
sub classify {
my ($f, $h) = (shift, {}); for (@_) { push @{$h->{$f->($_)}}, $_ } return $h;
} sub suffixes {
my $str = shift; map { substr $str, $_ } 0 .. length($str) - 1;
} sub suffix_tree {
return +{} if @_ == 0; return +{ $_[0] => +{} } if @_ == 1; my $h = {}; my $classif = classify sub { substr shift, 0, 1 }, @_; for my $key (sort keys %$classif) { my $subtree = suffix_tree( grep "$_", map { substr $_, 1 } @{$classif->{$key}} ); my @subkeys = keys %$subtree; if (@subkeys == 1) { my $subkey = shift @subkeys; $h->{"$key$subkey"} = $subtree->{$subkey}; } else { $h->{$key} = $subtree } } return $h;
}
print +Dumper suffix_tree suffixes 'banana$';</lang>
- Output:
$VAR1 = { '$' => {}, 'a' => { '$' => {}, 'na' => { 'na$' => {}, '$' => {} } }, 'banana$' => {}, 'na' => { 'na$' => {}, '$' => {} } };
Perl 6
<lang Perl 6>multi suffix-tree(Str $str) { suffix-tree map &flip, [\~] $str.flip.comb } multi suffix-tree(@a) {
hash @a == 0 ?? () !! @a == 1 ?? @a[0] => [] !! gather for @a.classify(*.substr(0, 1)) { my $subtree = suffix-tree(grep *.chars, map *.substr(1), .value[]); if $subtree == 1 { my $pair = $subtree.pick; take .key ~ $pair.key => $pair.value; } else { take .key => $subtree; } }
}
sub edges($tree) {
gather for $tree[] { .take for .key, edges .value; }
}
say sort edges suffix-tree 'banana$';</lang>
Output matches the one in the task description.
Extra credit: <lang Perl 6>my $tree = root => suffix-tree 'banana$'; .say for visualize-tree $tree, *.key, *.value.list;</lang>
- Output:
root ├─$ ├─a │ ├─$ │ └─na │ ├─$ │ └─na$ ├─na │ ├─$ │ └─na$ └─banana$
Racket
See Suffix trees with Ukkonen’s algorithm by Danny Yoo for more information on how to use suffix trees in Racket.
<lang racket>
- lang racket
(require (planet dyoo/suffixtree)) (define tree (make-tree)) (tree-add! tree (string->label "rosettacode$")) (for ([i (in-naturals)]
[c (node-children (tree-root tree))]) (printf "~a: ~a\n" i (label->string (node-up-label c))))
</lang> Output: <lang racket> 0: $ 1: e 2: de$ 3: o 4: code$ 5: acode$ 6: t 7: settacode$ 8: rosettacode$ </lang>