Our great sponsors
-
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].
-
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.
-
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:
-
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...