Skip to content

Instantly share code, notes, and snippets.

@max-mapper
Last active April 28, 2019 03:55
Show Gist options
  • Save max-mapper/5845846 to your computer and use it in GitHub Desktop.
Save max-mapper/5845846 to your computer and use it in GitHub Desktop.
trie implementations on npm

a trie (aka prefix trie) is a way of storing string values such that for an input string (e.g. autocomplete) all matching stored values can be re__trie__ved efficiently

listed alphabetically:

  • burst-trie - burst trie implementation, seems to be written in a Java style, no readme, not sure how fast it is
  • datrie - double array trie - a trie that uses arrays instead of objects for faster + smaller serialization
  • dtrie - trie based on minimal automaton, has stress tests, API is coupled to node though (requires fs)
  • glob-trie - trie with pattern matching expressions like * ? \ etc, has stress tests
  • iptrie - radix/patricia trie implementation specifically for IPv4 and IPv6 addresses
  • marisa-trie - bindings for the marisa-tree c++ library
  • path-trie - makes a trie from a object full of path keys with values e.g. { 'a/b/c': 'foo' }
  • persistent-hash-trie - trie inspired by functional persistent data structures, has benchmarks
  • prefix-tree - simple trie for fast autocomplete. no readme but has basic tests and a simple API
  • retrie - input words, get optimized regexes for trie matching
  • trie - serializes, deserializes, add/remove words (no value storage), test a prefix
  • triejs - trie.add(word, data), trie.find(word) => data
  • triecomplete - high level autocomplete API that uses a trie internally, has benchmarks, but seems unmaintained (lots of missing info, no issues etc)
@kemitchell
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment