Metadata-Version: 2.4
Name: pygstlib
Version: 0.1.0
Summary: Generalized suffix tree library (Python port of gstlib)
Author: Guillaume Dubuisson Duplessis
License-Expression: MIT
Project-URL: Homepage, https://github.com/GuillaumeDD/pygstlib
Project-URL: Source, https://github.com/GuillaumeDD/pygstlib
Project-URL: Changelog, https://github.com/GuillaumeDD/pygstlib/blob/main/CHANGELOG.md
Project-URL: Issues, https://github.com/GuillaumeDD/pygstlib/issues
Keywords: suffix tree,generalized suffix tree,ukkonen,lca,substring
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Classifier: Topic :: Text Processing :: Indexing
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE.txt
Provides-Extra: dev
Requires-Dist: pytest; extra == "dev"
Requires-Dist: pytest-cov; extra == "dev"
Provides-Extra: bench
Requires-Dist: notebook; extra == "bench"
Requires-Dist: nbconvert; extra == "bench"
Requires-Dist: ipykernel; extra == "bench"
Requires-Dist: matplotlib; extra == "bench"
Requires-Dist: pandas; extra == "bench"
Requires-Dist: numpy; extra == "bench"
Dynamic: license-file

# pygstlib: Generalized Suffix Tree Library in Python

pygstlib is a Python port of [gstlib](https://github.com/GuillaumeDD/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

```sh
uv add pygstlib    # or: pip install pygstlib
```

For development (editable install from a clone):

```sh
uv pip install -e .
```

## Usage

### Suffix Tree

```python
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

```python
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

```python
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

```sh
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:

```sh
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:

```sh
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](https://github.com/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](https://hal.archives-ouvertes.fr/hal-01436052)
  [DOI](https://dx.doi.org/10.1007/978-3-319-56608-5_16)\]

## License

MIT - see the LICENSE.txt file.

pygstlib is a port of [gstlib](https://github.com/GuillaumeDD/gstlib)
(copyright LIMSI-CNRS, CeCILL-B license), whose original work and
contributors are credited in accordance with the CeCILL-B attribution
requirement.
