SuffixTree - Efficient string manipulation data structure interface for Perl.
use SuffixTree; my $str = "mississippi"; my $tree=create_tree($str); print_tree($tree); my $position = find_substring($tree, "ssis"); printf("\nPosition of ssis in mississippi is %ld.\n\n", $position); delete_tree($tree); # NOTICE: this method will soon become deprecated
use SuffixTree; my $str = "mississippi"; my $tree=ST_CreateTree($str, length($str)); ST_PrintTree($tree); my $position = ST_FindSubstring($tree, "ssis", 4); printf("\nPosition of ssis in mississippi is %ld.\n\n", $position); ST_DeleteTree($tree);
The intention of this project is to provide an open-source implementation for an efficient data structure for strings manipulation - the Suffix Tree.
The code was written with as much consistency with the theoretical algorithm as possible (see references). It provides a set of interface functions for creating and searching the tree.
The suffix tree is implemented in ANSI-C. The code is written based on the original algorithm by E.Ukkonen. This is the Perl interface for the underlying ANSI-C implementation.
All functions are exported by default. Please note that all these interface functions were automatically extracted from the ANSI-C header file, so they might not behave as Perlish as you'd expect them to. This is something we will definitly address in the future.
Allocates memory for the tree and starts Ukkonen's construction algorithm. Parameters: A string. Returns a reference to the tree.
Searches for a string in the tree. It traverses the tree down starting its root like in a regular trie. Parameters: the tree to search in, a substring to look for. Returns the 1-based position it was found in the source string or 0 if string is not in the tree.
Prints the tree. Parameters: the tree to print.
Deletes a suffix tree. Parameters: the tree to delete. Returns : void.
All functions are exported by default. Please note that all these interface functions were automatically extracted from the ANSI-C header file, so they might not behave as Perlish as you'd expect them to. This is something we will try to address in the future.
Allocates memory for the tree and starts Ukkonen's construction algorithm. Parameters: A string, length of the string. Returns a reference to the tree.
Searches for a string in the tree. It traverses the tree down starting its root like in a regular trie. Parameters: the tree to search in, a substring to look for, length of substring. Returns the 1-based position it was found in the source string or 0 if string is not in the tree.
This Perl interface was mostly built automatically (using SWIG). Little to no attention was given to testing. In future relases of this Perl Module (along with its underlying ANSI-C implementation) we hope to fix all problems that might currenly interfere with successful usage of this module. Please send bug reports to the current maintainer(s) of this module.
[1] A better Perl-ish interface
[2] Building tests for this module (for the `make test` part of the installation)
[3] Object Oriented like usage
Please read the README file for information.
L<https://github.com/daoswald/SuffixTree.git> - This module's Github repository. L<http://en.wikipedia.org/wiki/Suffix_tree> - Wikipedia's Suffix Tree explanation.
Shlomo Yona <yona@cs.technion.ac.il> is the original author.
David Oswald <davido@cpan.org> is the current maintainer.
Offer Kaye for useful ideas and support.
Copyright (c) 2002, 2003, 2012 Shlomo Yona. All rights reserved.
This library is free software; you can redistribute it and/or modify it under the terms of either: the GNU General Public License as published by the Free Software Foundation; or the Artistic License.
See http://dev.perl.org/licenses/ for more information.
To install SuffixTree, copy and paste the appropriate command in to your terminal.
cpanm
cpanm SuffixTree
CPAN shell
perl -MCPAN -e shell install SuffixTree
For more information on module installation, please visit the detailed CPAN module installation guide.