BurntSushi

fst

Rust2015–2025

BurntSushi / fst

fst

Represent large sets and maps compactly with finite state transducers.

Explore on GitHub Read Hacker News discussions

11Distinct people

12Mentions

0Explicit recommenders

2.1KGitHub stars

REPOSITORY AT A GLANCE

What to know before exploring

What it is

Represent large sets and maps compactly with finite state transducers.

GitHub

Where it is used

No documented product use was verified in the last source check.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 3:56:07 PM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year12 dated mentions

Observed mentions: 2015-09-20 22:27:24 UTC to 2025-10-09 20:56:03 UTC.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges

UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
Period	Start (UTC)	End (exclusive, UTC)	Mentions	Submissions	Comments
2015	2015-01-01 00:00:00 UTC	2016-01-01 00:00:00 UTC	1	0	1
2016	2016-01-01 00:00:00 UTC	2017-01-01 00:00:00 UTC	1	0	1
2017	2017-01-01 00:00:00 UTC	2018-01-01 00:00:00 UTC	0	0	0
2018	2018-01-01 00:00:00 UTC	2019-01-01 00:00:00 UTC	2	0	2
2019	2019-01-01 00:00:00 UTC	2020-01-01 00:00:00 UTC	0	0	0
2020	2020-01-01 00:00:00 UTC	2021-01-01 00:00:00 UTC	0	0	0
2021	2021-01-01 00:00:00 UTC	2022-01-01 00:00:00 UTC	3	0	3
2022	2022-01-01 00:00:00 UTC	2023-01-01 00:00:00 UTC	1	0	1
2023	2023-01-01 00:00:00 UTC	2024-01-01 00:00:00 UTC	2	1	1
2024	2024-01-01 00:00:00 UTC	2025-01-01 00:00:00 UTC	1	0	1
2025	2025-01-01 00:00:00 UTC	2026-01-01 00:00:00 UTC	1	0	1

What Hacker News says

12 sources

Xeoncross·Oct 9, 2025

I really liked the README, that was a good use of AI. If you're interested in the idea of writing a database, I recommend you checkout https://github.com/thomasjungblut/go-sstables which includes sstables, a skiplist, a recordio format and other database building blocks like a write-ahead log. Also https://github.com/BurntSushi/fst which has a great Blog post explaining it's compression (and been ported to Go) which is really helpful for autocomplete/typeahead when recommending searches to users or doing spelling correction for search inputs.

In Show HN: I wrote a full text search engine in Go

antonhag·Apr 24, 2024

I don't actively use it, unfortunately. The main inspiration was to faster sort inputs into the https://github.com/BurntSushi/fst crate, which I in turn used to try to build a search library.

In American flag sort

tosh·Dec 6, 2023Submission

fst: Represent large sets and maps compactly with finite state transducers

3 points · Open discussion

nextaccountic·Aug 29, 2023

If the keys are strings and you can use Rust, have you considered fst [0]? If the keys have prefixes in common, it is very compact. There's a blog post about it [1] [0] https://github.com/BurntSushi/fst [1] https://blog.burntsushi.net/transducers/ The main limitation of it is that it doesn't support removal, but if removals are infrequent you can workaround that with another fst with removed items (and periodically rebuild the whole thing)

In Designing a new concurrent data structure

ggordonhall·Aug 1, 2022

bloop (YC S21) | Senior Software Engineer (Rust) | Full Time | Remote or London (Visa Sponsor) We're bringing neural code search to the masses. To do this we're developing efficient, fast indexing and retrieval mechanisms that enable lightning-fast search and scale to massive amounts of code. As a Senior Software Engineer you'll work at the heart of this, collaborating with a small, talented team to design and implement the core engine that powers bloop search. You'll work on the forefront of information retrieval and data storage, using techniques pioneered in academia and the latest open source search projects and developing some of your own too! You'll get to show off too, as we will open-source the first version of the engine. You'll love what we're working on if you're interested in the implementation of: - https://github.com/quickwi

Read the rest

t-oss/tantivy - https://github.com/meilisearch/meilisearch - https://github.com/BurntSushi/fst You'll be joining a small group of engineers who are obsessed with the challenges posed by search, and who want to build tools to improve the process of writing and maintaining software. More retails about the role here: https://bloop.jobs.personio.com/job/748329?display=en Apply by emailing join@bloop.ai or through the Personio link.

In Ask HN: Who is hiring? (August 2022)

sitkack·Jul 31, 2021

I realize I wasn't clear. I used 2 sqlite databases just to store the article titles and offsets into binary files (<2GB) that had chunks of compressed data. Each chunk contained 10s-100s of stories, so that the decompressed around was around 20megs I believe. I had planned to store everything in sqlite, but there were too many issues. The FTS extension to sqlite is excellent, it made whole classes of problems literally melt away. Recalling now, the article text itself, I stored in groups of articles concatenated together so that that data compression could take advantage of similar texts. This data was just Lua data structures, with the article title and article body in an array. So I knew which chunk it was in, but I had to decompress a whole chunk at a time and then iterate through the list of decompressed articles to find the specifi

Read the rest

c one. I was trying to tune search time, decompression time and compression ratio. I had a handful of parameters in the job that would take the xml dumps and create the sqlite and compressed blobs. Memory consumption would spike as a chunk was decompressed, but after a call to the Lua garbage collector after pulling the article out of the decompression buffer, everything was fine again. This was late 2010 or so. The job that processed the XML into database+bin data took over an hour to run on my laptop. If I did it again, I'd use a compression library that was tuned for decompression and used an external dictionary. For the index, I'd use fst [1] The project stalled out in parsing the wikitext, there are now libraries that can handle the parsing. I have considered resurrecting it, with jpeg2000 or other image codecs, one could include the images as well. The system did not have FTS over the article text itself. I had planned to use some sort tree of bloom filters, something similar to [2]. I was really trying to keep the total footprint of all the data under 10G or so it could fit on the majority of devices. Now with larger flash sizes, better codecs and better compression libraries, the functionality and performance could be greatly enhanced. I learned a ton from this project, I really recommend getting deep into something, but also working within your limits and having fallback plans when something looks insurmountable. There were plenty of times where I thought I was a dead end, only to say, "what if ..." the next day, run a quick experiment and be on to the next insurmountable roadblock. [1] https://github.com/BurntSushi/fst [2] https://arxiv.org/abs/2002.03057

In Show HN: Static.wiki – read-only Wikipedia using a 43GB SQLite file

Palmik·Mar 26, 2021

Hi folks, WordBueno is a dictionary that aims to be multilingual, fast and simple. The original goal was to build a tool to facilitate finding a new domain name (e.g. checking what a word means in different languages to make sure it’s not a swear word, finding synonyms, translations, rhymes, etc.), somehow it devolved into just a dictionary. How it works: WordBueno’s data is currently derived from Wiktionary. The backend is using Rust’s warp [1] with fst [2] for indexing. The front-end is built in TypeScript with Svelte. I use prerender [3] for server-side rendering to facilitate crawling. I wrote a bit more about it at https://wordbueno.com/about and I would be happy to answer any questions. I am curious to hear what you think. Some thoughts: - Exposing API? “Is word X a swear word in any language?”, “Synonyms for X”, etc. - Searching by

Read the rest

regex? Feasible with a special index. - Browser extension? Embedded in the “new tab” page and right-click contextual menu lookup. - The current data is lacking in many ways. Missing synonyms / antonyms / translations / examples / words. I am considering enhancing it in some ways (e.g. joining it with WordNet, etc.). - Wiktionary is inherently unstructured, this makes it hard to process and leverage its full potential, it would be great if it was built in a structured way from the group up (ala Wikidata?). [1] https://github.com/seanmonstar/warp [2] https://github.com/BurntSushi/fst [3] https://palmik.net/universal-ssr/

In Show HN: WordBueno: sleek dictionary built with Rust and Svelte

burntsushi·Mar 13, 2021

No you don't. I've written multiple programs that load things instantly off the file system via memory maps. See the fst crate[1], for example, which is designed to work with memory maps. imdb-rename[2] is a program I wrote that builds a simple IR index on your file system that can then instantly search it by virtue of memory maps. Rust "works badly with memory mapped files" doesn't mean, "Rust can't use memory mapped files." It means, "it is difficult to reconcile Rust's safety story with memory maps." ripgrep for example uses memory maps because they are faster sometimes, and its safety contract[3] is a bit strained. But it works. [1] - https://github.com/BurntSushi/fst/ [2] - https://github.com/BurntSushi/imdb-rename [3] - https://docs.rs/grep-searcher/0.1.7/grep_searcher/struct.Mma...

In Speed of Rust vs. C

bpicolo·Sep 9, 2018

Their FST library is also awesome https://github.com/BurntSushi/fst

In XSV: A fast CSV command-line toolkit written in Rust

PSeitz·Feb 27, 2018

I use a state machine for text https://github.com/BurntSushi/fst

In Why Developers Never Use State Machines (2011)

mitchtbaum·Dec 24, 2016

I'm moving toward Lua only scripting, backed by Rust only system commands (at least in model space for now). From that approach, I intend to solve this Shell use case with https://github.com/BurntSushi/fst and any needed Lua syntax extensions, like http://lua-users.org/wiki/StringInterpolation , http://lua-users.org/wiki/VarExpand , etc. So far, I have some stacks of notes on Rust replacements and some links to Lua dialogues on similar (failed) attempts for a new shell. If you have any more points of interest or a drive to implement it, cool.

In Set Operations in the Unix Shell (2008)

burntsushi·Sep 20, 2015

> besides finite state dictionaries, ..., String mappings based on perfect hash automata I'm implementing a similar library in Rust. One of the key things I've found missing in Daciuk's great work on the topic is the handling of the registry. In your code[1], it looks like you're using a straight a hash table. I thought you'd like to know that I've had great success sacrificing complete DFA minimization in exchange for a small constant memory overhead by using an LRU cache of only some classes of states. My code still needs a good deal of polish, and I intend to write a blog post, but I bet you can make sense of the general strategy from the code and reuse it.[2] N.B. Lucene's implementation permits sacrificing complete minimization, but they don't use an LRU cache and I think still permit the registry to grow without bound. [1] - https:/

Read the rest

/github.com/danieldk/dictomaton/blob/master/src/main/... [2] - https://github.com/BurntSushi/fst/blob/master/src/fst/regist... (The data type is a map from node hash to LRU cache. That is, there is a small LRU cache for each bin in the map.)

In Implementing Levenshtein Automata