pygstlib: Generalized Suffix Tree Library in Python

pygstlib is a Python port of gstlib, a library that implements a generalized suffix tree datastructure for sequences of items.

Features:

• efficient building of suffix trees and generalized suffix trees;
• efficient search of a pattern in (generalized) suffix trees;
• efficient computation of longest common subsequence of two sequences;
• linear-time solution to the multiple common substring problem.

It implements the following algorithms from the book "Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology" by D. Gusfield:

• Ukkonen's algorithm for building generalized suffix trees;
• constant-time lowest common ancestor (LCA) retrieval (Schieber and Vishkin approach) via a linear-time preprocessing of the tree;
• a linear-time solution to the multiple common substring problem (Lucas Hui approach).

Sequences may be str, list, tuple or any sliceable sequence of hashable items. Results are returned with the same type as the inserted sequences whenever possible.

Installation

uv add pygstlib    # or: pip install pygstlib

For development (editable install from a clone):

uv pip install -e .

Usage

Suffix Tree

from pygstlib import SuffixTree

# Building the suffix tree
text = "String to be searched"
stree = SuffixTree(text)

# Searching for a pattern
pattern = "to be"
stree.contains(pattern)  # True (or: pattern in stree)

indexes = stree.find(pattern)  # [7]
first = indexes[0]

stree.sequence[first:first + len(pattern)]
# 'to be'

# Traversing the suffixes
for suffix in stree.suffixes():
    print(suffix)

# It is possible to build a suffix tree for a wide variety of sequences!
sentence = text.split(" ")  # ['String', 'to', 'be', 'searched']
stree_sentence = SuffixTree(sentence)

pattern_sentence = ["be", "searched"]

stree_sentence.contains(pattern_sentence)  # True

indexes_sentence = stree_sentence.find(pattern_sentence)  # [2]
first_sentence = indexes_sentence[0]

stree_sentence.sequence[first_sentence:first_sentence + len(pattern_sentence)]
# ['be', 'searched']

stree_sentence.contains(["hello", "world", "!"])  # False

Generalized Suffix Tree

from pygstlib import GeneralizedSuffixTree

# Building a generalized suffix tree
#
# Here:
# - a sequence is a list of strings, and
# - an item is a string
utterances = [
    ["Hello", "world", "!"],
    ["How", "are", "you", "today", "?"],
    ["How", "are", "you", "doing", "?"],
    ["are", "you", "there", "?"],
    ["What", "a", "beautiful", "world", "!"],
]

gstree = GeneralizedSuffixTree(utterances)

# Searching the generalized suffix tree
pattern = ["are", "you"]
gstree.find(pattern)
# [(3, 0), (2, 1), (1, 1)]
# (3, 0) in "are", "you", "there", "?"
# (2, 1) in "How", "are", "you", "doing", "?"
# (1, 1) in "How", "are", "you", "today", "?"

# Computing the multiple common subsequences
for freq, subseq in gstree.bulk_multiple_common_subsequence():
    print(f"The sequence '{' '.join(subseq)}' is appearing in {freq} sequences")
# Output:
# The sequence 'are you' is appearing in 3 sequences
# The sequence '!' is appearing in 2 sequences
# The sequence '?' is appearing in 3 sequences
# The sequence 'How are you' is appearing in 2 sequences
# The sequence 'you' is appearing in 3 sequences
# The sequence 'world !' is appearing in 2 sequences

# Computing the longest common subsequences between a pattern and a
# generalized suffix tree
pattern2 = ["well", ",", "today", "?", "where", "are", "you", "?"]
for start, end, positions in gstree.find_longest_common_subsequences(pattern2):
    subsequence = " ".join(pattern2[start:end])
    print(f"Subsequence '{subsequence}' appears in:")
    for seq_id, start_pos in positions:
        sequence = " ".join(gstree.get_sequence(seq_id))
        print(f"\t- sequence {seq_id}: {sequence} at starting position {start_pos}")
# Output:
# Subsequence 'today ?' appears in:
#       - sequence 1: How are you today ? at starting position 3
# Subsequence 'are you' appears in:
#       - sequence 2: How are you doing ? at starting position 1
#       - sequence 1: How are you today ? at starting position 1
#       - sequence 3: are you there ? at starting position 0

# It is possible to build a generalized suffix tree for a wide variety
# of sequences!
#
# Here:
# - a sequence is a string, and
# - an item is a character
gstree2 = GeneralizedSuffixTree(["ABCDEF", "CDE", "EFGHIJK", "LMNOPQRST", "STUVWXYZ"])
gstree2.contains("E")  # True
gstree2.find("E")
# [(1, 2), (2, 0), (0, 4)]
# (1, 2) in CDE
# (2, 0) in EFGHIJK
# (0, 4) in ABCDEF

# Building a generalized suffix tree incrementally
gstree_foobar = GeneralizedSuffixTree()
gstree_foobar.add("foo")
gstree_foobar.add("bar")

gstree_foobar.contains("hello")  # False
gstree_foobar.contains("oo")     # True
gstree_foobar.contains("ba")     # True

Utils: Longest Common Subsequence

from pygstlib import longest_subsequence

longest_subsequence("abcd", "efgh")    # None

longest_subsequence("abcd", "cdefgh")  # 'cd'

Caveats

• One sequence type per tree. All sequences inserted into a tree must share the same type (str, list, ...); add raises TypeError otherwise. Results are returned with that type.
• Mutation invalidates live results. Iterators (suffixes(), bulk_multiple_common_subsequence()) and CommonSubsequences results raise RuntimeError when the tree is modified (add, clear) during/after their creation. Materialize results (e.g. list(...)) before mutating if you need them afterwards.
• Not thread-safe. Queries lazily (re)compute internal preprocessing structures, so even concurrent reads of the same tree must be synchronized externally.
• Degenerate inputs. Building and indexing are linear even on pathological inputs such as "a" * n; however materializing all common subsequences (iterating every result) is inherently bound by the total output size, which can be quadratic on such inputs.

Tests

uv run pytest

Benchmarks

This project includes benchmarks to assess the efficiency of some algorithms (building of the tree, solving of the multiple common subsequence problem) and to check that running time grows linearly with input size:

uv run python benchmarks/linearity.py            # characters: build + MCSP
uv run python benchmarks/linearity.py --tokens   # tokens: build only
uv run python benchmarks/linearity.py --all      # include the largest files

For a more thorough analysis (linear and log-log regressions, empirical complexity order, throughput plots), run the Jupyter notebook:

uv pip install -e '.[bench]'
# register the project environment as a Jupyter kernel (once)
uv run python -m ipykernel install --user --name pygstlib --display-name "Python (pygstlib)"
uv run jupyter notebook benchmarks/linearity_analysis.ipynb

The notebook is configured to use the pygstlib kernel registered above, so pygstlib and the benchmark dependencies resolve from the project environment regardless of how Jupyter itself was launched.

Files to benchmark the code come from the repository schmidda/ukkonen-suffixtree.

Contributors

Original Scala library (gstlib):

• Guillaume Dubuisson Duplessis (2016-present)
• Vincent Letard (2016)
• Torsten Rudolf (2020)

Usage for Research Purposes

If you use this library for research purposes, please make reference to this library by citing the following paper:

• Dubuisson Duplessis, G.; Charras, F.; Letard, V.; Ligozat, A.-L.; Rosset, S., Utterance Retrieval based on Recurrent Surface Text Patterns, 39th European Conference on Information Retrieval (ECIR), 2017, pp. 199--211 [More DOI]

License

MIT - see the LICENSE.txt file.

pygstlib is a port of gstlib (copyright LIMSI-CNRS, CeCILL-B license), whose original work and contributors are credited in accordance with the CeCILL-B attribution requirement.