npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

@jayrbolton/suffix-tree

v0.0.1

Published

A suffix tree string matching algorithm implementation in node

Downloads

41

Readme

suffix-tree

Suffix trees are useful for efficient string searching of suffixes and substrings. They're often used in bioinformatics on genomes. One big advantage is that you can search for the same suffix across many strings in linear time. This is an optimized implementation using Ukkonnen's algorithm and requires O(n) time and O(n) space to construct a tree for a string of length n.

You can can check whether a string is a substring of another, whether a string is a suffix of another (starting from any point), the number of occurrences of a substring, or you can find the longest repeated substring. You can also do these operations on a set of multiple strings in linear time.

Usage

var STree = require('@jayrbolton/suffix-tree')
var tree = STree.create('banana')
var suffixIndex = STree.findSuffix('ana') // -> 3
var substringIndex = STree.findSubstring('ana') // -> 1
var occurrences = STree.occurrences('ana') // -> 2
var longestRepeating = STree.longestRepeating() // -> 'ana'

You can view all tested strings in test/index.js -- if you have a string that you want to include in the test suite, please open an issue or pr.

API

STree.create(initialStr)

Initiialize a suffix tree. Returns a suffix tree object.

Optionally pass in an initial string to add to the tree

STree.create('banana')

STree.add(string, tree)

Add another, separate string to the tree. This will result in a single, larger tree that combines all strings into one tree.

Mutates the given tree and returns it.

const t = STree.create('banana')
STree.add('plantain', t)

STree.format(tree)

Return a formatted string for a tree to see how it looks. This creates an left indentation-based tree.

console.log(STree.foramt(tree))

STree.findSuffix(string, tree)

Find a given suffix for any string in the tree. Will return an array of indexes of strings that have the suffix. Returns an empty array if the suffix is not found.

You can get the string from its index by using getStringByIndex

const ids = STree.findSuffix('ana', tree)

STree.getStringByIndex(id, tree)

Return the original string based on its index

const t = STree.create('banana')
STree.add('plantain', t)
STree.getStringByIndex(0) // -> 'banana'
STree.getStringByIndex(1) // -> 'plantain'

STree.allSuffixes(tree)

Return an array of arrays of ALL suffixes for the entire tree. Traverses every path of the tree

STree.longestCommonSubstring(tree)

Get the longest common substring among all strings in a tree. Returns the actual string.

const t = STree.create('plantain')
STree.add('entertain', t)
const s = STree.longestCommonSubstring(t) // -> 'tain'

STree.findSubstrings(string, tree)

Find all occurrences of a substring in any string in the tree. Returns an object where:

  • Each key in the object is an index to a string in the tree (use getStringByIndex to get the string)
  • Each value in the object is an array of starting indexes for the substring occurrences in the string
const t = STree.create('banana')
const occs = STree.findSubstrings('an', t) // -> {0: [1, 3]}
// We found occurences in string 0 ('banana'), at starting indexes 1 and 3 inside 'banana'

Un-implemented functions

Suffix trees have a lot of other efficient functions that can be written for them. See the Wikipedia page for a comprehensive list of these functions. They could either be added to this module or created in independent modules.

Install

With npm installed, run

$ npm install @jayrbolton/suffix-tree

See Also

License

MIT