README

===============================================================================
Note from JDonner -- this is pretty much defunct, a simple test crashes and I'm
too lazy to try to penetrate the SWIG to figure it out. I'm going to leave it
up, because I hate to take code off the net, (plus I don't see how to, via
github anyway :/ (maybe because it's been forked)).

Plus the license is dubious, probably academic. I've emailed the original
author, Dan Gusfield, and will update with his response.

There are plenty of other Python suffix trees out there nowadays (there weren't
when I grabbed this from Danny Yoo).  So, this is unsupported. Feel free to fork
it if you really must. I believe the underlying C code is sound, (though limited
to single-byte character data!) Maybe try re-wrapping it with a later version of
SWIG or re-doing it in Cython if you really want.
===============================================================================


SuffixTree --- A Suffix Tree library for Python

Conspirator: Danny Yoo (dyoo@hkn.eecs.berkeley.edu)

This is a SWIG wrapper around Dan Gusfield's 'strmat' suffix tree
library.

    http://www.cs.ucdavis.edu/~gusfield/strmat.html

Suffix trees allow for very powerful string matching, and are used
quite a bit in many elegant string algorithms.  Since this is a
wrapper around strmat.stree, most of the documentation in
doc/stree.doc should apply.


Here are the modules included in the SuffixTree package:

    o SuffixTree.SuffixTree -- The suffix tree structure.  This is a
      thin wrapper around strmat's stree data structure.  This isn't a
      complete wrapper yet; I need to find some time to complete this.
      The wrapper appears to be good enough for simple stuff.

      Methods of SuffixTree:

          o SuffixTree(alphabet=STREE_ASCII)

              Construct a new SuffixTree.  By default, the alphabet
              used by the SuffixTree is ASCII.  Other choices include
              STREE_DNA, STREE_RNA, and STREE_PROTEIN.

          o add(string, id)

              Adds a string to the suffix tree with an id.

          o root()

              Returns the root() SuffixNode of the tree.

          o num_nodes():

              Returns the total number of nodes held in the tree.

          o match(string)

              Given a string, traverse the suffix tree and return a
              3-tuple (match_length, suffix_node, endpos)
              
              

    o SuffixTree.SuffixNode  (I need to fix the documentation here)

        Methods of 
        num_children()
        find_child(char ch)
        children()
        next()
        parent()
        suffix_link()
        edgelen()
        edgestr()
        getch()
        labellen()
        labelstr()
        ident()
        num_leaves()
        leaf(int leafnum)



    o SuffixTree.SubstringDict -- An application of suffix trees toward
      substring matching.  An example might help:

        ###
        >>> import SuffixTree.SubstringDict
        >>> d = SuffixTree.SubstringDict()
        >>> d['foobar'] = 1
        >>> d['barfoo'] = 2
        >>> d['forget'] = 3
        >>> d['arfbag'] = 4
        >>> d['a']
        [4, 2, 1]
        >>> d['arf']
        [2, 4]
        >>> d['oo']
        [2, 1]
        >>> d['food']
        []
        ###

      SubstringDict provides a mapping that allows for substrings of
      keys.  The keys do need to be strings though.