Index 1.6B Keys with Automata and Rust (2015)

Interesting stuff. The article is quite verbose -- here is the Cliff Notes versions: The trie is a well-known data structure for storing string sets or string-keyed maps (https://en.wikipedia.org/wiki/Trie). You can compress a trie by using a DAG/FSM instead of a tree -- this lets you share states for suffixes, whereas trees only let you share states for prefixes. But for large sets minimizing a DAG is too expensive to perform on the whole trie. If you insert the keys…

The FST mechanism for using an acyclic graph to store information is very reminiscent of GADDAG[1] structure for Scrabble dictionaries. In my search for interesting problems in the compression space, I ran into quite a lot of genomics research which suggests combining a compression algorithm with a lookup method, because identifying common items between samples reduces both storage and speeds up lookup. > An FST based data structure as presented in this article does not have this capability. Namely, once…

This is the same individual who spent over two years writing a faster grep than grep: http://blog.burntsushi.net/ripgrep/ Amazing work.

(with proper formatting this time) Note that it is perfectly possible to have more complicated values associated with FST keys, just not in the https://docs.rs/fst/0.3.3/fst/map/index.html implementation. FST's can also be cyclic – this lets you represent things you couldn't with just a hash table. ----- Anyone who wants to play around with this should try the HFST[1] library, which lets you create compact and possibly cyclic string-to-string maps, which are closed under union, intersection, reversal, inversion…