Trie in JavaScript: The Data Structure Behind Autocomplete

This page summarizes the projects mentioned and recommended in the original post on news.ycombinator.com

Our great sponsors
  • WorkOS - The modern identity platform for B2B SaaS
  • InfluxDB - Power Real-Time Data Analytics at Scale
  • SaaSHub - Software Alternatives and Reviews
  • Typesense

    Open Source alternative to Algolia + Pinecone and an Easier-to-Use alternative to ElasticSearch ⚡ 🔍 ✨ Fast, typo tolerant, in-memory fuzzy Search Engine for building delightful search experiences

    There is another aspect of tries that make them really useful: you can do fast, fuzzy word searches on a trie.

    In Typesense[1], I've implemented fuzzy search based on levenshtein damerau distance and it's incredibly fast. I've found this approach to be a much better alternative to Peter Norvig's brute-force based spell-checker that is quite a popular post [2].

    [1]: https://github.com/typesense/typesense

  • trie

    A fast trie implementation for typescript (by shortwave)

    Tries are fun structures!

    However, for autocomplete you often want a weighted Trie because you have extra information you want to weight nodes by. An example with contacts is that you often want recent and frequent contacts.

    My company has an open source trie implementation here for a client to do weighted contact auto complete: https://github.com/shortwave/trie

  • WorkOS

    The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.

  • fast-trie-js

    Fast Javascript Trie data structure

    I wrote a little Trie in Javascript for practice a while back. It flattens the data into a single array for better locality. I think it ends up being pretty quick for lookups (but not insertions).

    https://github.com/mgraczyk/fast-trie-js/blob/master/index.j...

    I used it for this little demo:

    https://assets.opentoken.com/demos/search/index.html

  • pyroscope

    Discontinued Continuous Profiling Platform. Debug performance issues down to a single line of code [Moved to: https://github.com/grafana/pyroscope] (by pyroscope-io)

    Tries are also used to efficiently store names of functions in macOS / iOS binaries (Mach-O format) and work great for that purpose because a lot of functions have the same prefixes [0].

    Indexes in mongodb use a similar concept (they call that prefix compression [1]), and that allows them to store indexes more efficiently.

    We use them at Pyroscope and we wrote a blog post about our storage design [2] It has some animations too!

    [0] https://www.m4b.io/reverse/engineering/mach/binaries/2015/03...

    [1] https://docs.mongodb.com/manual/reference/glossary/#std-term...

    [2] https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto...

NOTE: The number of mentions on this list indicates mentions on common posts plus user suggested alternatives. Hence, a higher number means a more popular project.

Suggest a related project

Related posts