weedyseadragon / suffixtree Goto Github PK

SuffixTree --- A Suffix Tree library for Python

Conspirator: Danny Yoo ([email protected])

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.

Installation:

   1. Download
   2. Compile:  > python setup.py build

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.