Index 1,600,000,000 Keys with Automata and Rust - Andrew Gallant's Blog
burntsushi.net · 18,899 words · saved by 2 readers
I blog mostly about my own programming projects.
It turns out that finite state machines are useful for things other than expressing computation. Finite state machines can also be used to compactly represent ordered sets or maps of strings that can be searched very quickly. In this article, I will teach you about finite state machines as a data structure for representing ordered sets and maps. This includes introducing an implementation written in Rust called the fst crate . It comes with complete API documentation . I will also show you how to build them using a simple command line tool. Finally, I will discuss a few experiments culminating
saved by
related reading
- Finite-state transducer - Wikipediaen.wikipedia.org
- CRDTs go brrrjosephg.com
- Build Your Own Databasenan.fyi
- Yudhister Kumaryudhister.me
- NYSRGnotes.ekzhang.com
- Rust Iterator Cheat Sheetdanielkeep.github.io
- Faiss: A library for efficient similarity search - Engineering at Metaengineering.fb.com
- Trie - Wikipediaen.wikipedia.org
- Beating the fastest lexer generator in Rustalic.dev
- Role Of Algorithmsmatklad.github.io
- Static search trees: 40x faster than binary search · CuriousCodingcuriouscoding.nl
- GitHub - jackyzha0/bft-json-crdt: 🏰 the first JSON-like Byzantine Fault Tolerant CRDTgithub.com