Lecture
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.
We will look at 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. We will also look at how to build them with a simple command-line tool. We will examine several experiments that ended with indexing more than 1,600,000,000 URLs (134 GB) from a common crawl archive.
The technique presented in this article also shows how Lucene represents part of its inverted index.
Along the way we will talk about memory maps, intersecting automata with regular expressions, fuzzy search with Levenshtein distance, and streaming set operations.
Target audience: some familiarity with programming and fundamental data structures. Experience with automata theory or Rust is not required.
As a teaser to show where we are heading, let us briefly look at an example. We will not tackle 1,600,000,000 keys just yet. Instead, we will consider ~16,000,000 Wikipedia article titles (384 MB). Here is how to index them:
$ time fst set --sorted wiki-titles wiki-titles.fst real 0m18.310
The resulting index, wiki-titles.fst, is 157 MB. For comparison, gzip takes 12 seconds and compresses to 91 MB. (For some datasets our indexing scheme can beat gzip in both speed and compression ratio.)
However, here is what gzip cannot do: quickly find all article titles that start with Homer the:
$ time fst grep wiki-titles.fst 'Homer the.*' Homer the Clown Homer the Father Homer the Great Homer the Happy Ghost Homer the Heretic Homer the Moe Homer the Smithers ... real 0m0.023s
For comparison, running grep on the original uncompressed data takes 0.3 seconds.
And finally, here is something even grep cannot do: quickly find all article titles within a certain edit distance of Homer Simpson:
$ time fst fuzzy wiki-titles.fst --distance 2 'Homer Simpson' Home Simpson Homer J Simpson Homer Simpson Homer Simpsons Homer simpson Homer simpsons Hope Simpson Roger Simpson real 0m0.094s
This article is quite long, so if you came here only for the fun stuff, you can jump straight to the section where we index 1,600,000,000 keys.
The first section covers finite state machines and their use as data structures in abstract form. This section is meant to give you a mental model with which to reason about the data structure. There is no code in this section.
The second section uses the abstraction developed in the first section and demonstrates its implementation. This section is mostly meant as an overview of how to use my fst library. This section contains code. We will discuss some implementation details, but avoid getting into the weeds. You can skip this section if you do not care about code and just want to see experiments with real data.
The third and final section demonstrates the use of a simple command-line tool for building indexes. We will look at some real datasets and try to reason about the performance of finite state machines as a data structure.
Comments