typescript-algos v1.0.45

Typescript-algos

Small collection of both common and uncommon data structures written in typescript and published for convenience and use in my projects. Most of the data structures are based off of implementations from Introduction to Algorithms and were written for clarity rather than efficiency. The Aho Corasick implementation is based off of Stanford's CS166: Data Structures slides. The completion trie is a modified implementation of the Completion Trie presented in the paper Space-efficient data structures for Top-k completion (2013).

Feel free to use these for your own projects but unless you're using one of the starred algorithms I recommend using the implementations from mnemonist. If you are using one of the starred algorithms I'd love to know what you're building!

I've starred (⭐️) the algorithms which I find interesting.

• AhoCorasick ⭐️
  • Implementation of Aho-Corasick algorithm an amazing algorithm for string matching when you have a large static number of patterns to match in a small to medium and dynamic text.
  • Given a set of N pattern strings and an input text of length m we can find all z instances of the pattern strings in the text in time O(m+z). Note that the number of pattern strings has no impact on the run time!
• BinarySearchTree
• CompletionTrie ⭐️
  • Very efficient top-K completions from a trie
  • Given an alphabet of size E, a prefix p, a number of requested completions k, and L where L is the average length of the completions excluding the common prefix p, returns the top k completions in time O(Ep + kL log(kL)). If we replace these numbers with some common values, say E=26, k=10, L=9, and p=1 we can find top-k completions in approx. 430 steps. Note that the number of prefix matches does not factor into the Big O time. The brute force topk would involve finding all matching entries (p + M*L) where p is the prefix, L is the average length of completions excluding the common prefix p and M is the number of matches plus M log(M) to sort the matches. For even a small number of matches say M=1000, p=1, L=9 this is approximately 16000 steps.
  • has rudimentary collision support where multiple values can be added with the same key. The collision support does not retain the same algorithmic guarantees outlined above.
• CompressedTrie ⭐️
  • An implementation of a Trie where edges can contain more than one symbol at a time. Can greatly reduce the size of the trie under certain circumstances
• Heap
• LinkedList
• Queue
• Stack
• Trie

Some of these data structures have methods for supporting serialization. If you want to try to serialize these data structures yourself and are running into circular reference issues, consider using flatted. I've had moderate success with flatted and ran into Maximum callstack size exceeded errors but those issues may be resolved.

Installation

npm install typescript-algos

Usage

import { LinkedList } from "typescript-algos";

const linkedList = new LinkedList([...Array(10).keys()]);

Releases

Commit your changes.
Run npm version patch && npm publish
Git Push