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
- Rust Language Cheat Sheetcheats.rs
- A half-hour to learn Rustfasterthanli.me
- Beating the fastest lexer generator in Rustalic.dev
- Build Your Own Databasenan.fyi
- Fast and Simple Rust Internermatklad.github.io
- Fast regex search: indexing text for agent tools · Cursorcursor.com
- Static search trees: 40x faster than binary search · CuriousCodingcuriouscoding.nl
- Building a BFT JSON CRDTjzhao.xyz
- Rust Iterator Cheat Sheetdanielkeep.github.io
- Finite-state transducer - Wikipediaen.wikipedia.org
- Working with strings in Rustfasterthanli.me
- Building a fast Electron app with Rustkeminglabs.com