suffix-tree

A Generalized Suffix Tree for any iterable, with Lowest Common Ancestor retrieval

These details have not been verified by PyPI

Project links

Homepage

Project description

A Generalized Suffix Tree for any Python iterable, with Lowest Common Ancestor retrieval.

pip install suffix-tree

This suffix tree:

works with any Python iterable, not just strings, if the items are hashable,
is a generalized suffix tree for sets of iterables,
uses Ukkonen’s algorithm to build the tree in linear time,
does constant-time Lowest Common Ancestor retrieval,
outputs the tree as GraphViz .dot file.

Three different builders have been implemented:

one that follows Ukkonen’s original paper ([Ukkonen1995]),
one that follows Gusfield’s variant ([Gusfield1997]),
and one simple naive algorithm.

PyPi: https://pypi-hypernode.com/project/suffix-tree/

[Ukkonen1995]

Ukkonen, Esko. On-line construction of suffix trees. 1995. Algorithmica 14:249-60. http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

[Gusfield1997]

Gusfield, Dan. Algorithms on strings, trees, and sequences. 1997. Cambridge University Press.

Project details

These details have not been verified by PyPI

Project links

Homepage

Release history Release notifications | RSS feed

0.1.2

Oct 9, 2023

0.1.1

Oct 8, 2023

0.1.0

Oct 3, 2022

0.0.7

Feb 18, 2020

0.0.6

Jul 31, 2018

This version

0.0.5

Jul 30, 2018

0.0.4

Jul 7, 2018

0.0.3

Jul 7, 2018

0.0.2

Jul 2, 2018

0.0.1

Jul 1, 2018

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

suffix-tree-0.0.5.tar.gz (17.1 kB view details)

Uploaded Jul 30, 2018 Source

Built Distribution

suffix_tree-0.0.5-py3-none-any.whl (22.4 kB view details)

Uploaded Jul 30, 2018 Python 3

File details

Details for the file suffix-tree-0.0.5.tar.gz.

File metadata

Download URL: suffix-tree-0.0.5.tar.gz
Upload date: Jul 30, 2018
Size: 17.1 kB
Tags: Source
Uploaded using Trusted Publishing? No
Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.18.4 setuptools/39.2.0 requests-toolbelt/0.8.0 tqdm/4.23.4 CPython/3.6.6

File hashes

Hashes for suffix-tree-0.0.5.tar.gz
Algorithm	Hash digest
SHA256	`bbe8ed7def47825aa0d8555d885be9f6ead0229b48eec01dfa00b71c43db2d2d`
MD5	`4fef55f9595075fe32b3c09258b4b754`
BLAKE2b-256	`b6c3500267e2eee7c850bce270106218e78812fdc72bef5750f598c1c48ab23d`

See more details on using hashes here.

File details

Details for the file suffix_tree-0.0.5-py3-none-any.whl.

File metadata

Download URL: suffix_tree-0.0.5-py3-none-any.whl
Upload date: Jul 30, 2018
Size: 22.4 kB
Tags: Python 3
Uploaded using Trusted Publishing? No
Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.18.4 setuptools/39.2.0 requests-toolbelt/0.8.0 tqdm/4.23.4 CPython/3.6.6

File hashes

Hashes for suffix_tree-0.0.5-py3-none-any.whl
Algorithm	Hash digest
SHA256	`80789135a53002b9ea04b09d7e152d0c07b8608bacd0acc47cfb1588da4a3d5c`
MD5	`3d96b0b07a346faa9fb9f056e15b7c99`
BLAKE2b-256	`1853fde250854779a65ca3a7ce3e750e767cf2ead30447a840f06015512b9a25`