Lecture
The fst crate (Rust's word for "compilation units") is something I built. It is written in Rust, fast, and memory-conscious. It provides two convenient abstractions around ordered sets and ordered maps, and also gives direct access to the underlying finite state transducer. Loading sets and maps using memory maps is a first-class feature, which makes it possible to query sets or maps without first loading the entire data structure into memory.
The capabilities of ordered sets and maps mirror those of BTreeSet and BTreeMap in Rust's standard library. The key difference is that fst sets and maps are immutable, keys are fixed to byte sequences, and the values of maps are always 64-bit unsigned integers.
In this section we will cover the following topics:
This section will therefore contain a great deal of Rust code. I will do my best to include high-level descriptions of what is happening in the code, so that you do not need to know Rust to follow what is going on. That said, to get the most out of this section, I would recommend reading the excellent book on the Rust programming language.
In addition, you may find it useful to keep the fst API documentation at hand, which can serve as a good complement to the material in this section.
Most data structures in Rust are mutable, which means that queries, insertions and deletions are neatly combined in a single API. Data structures built on the FSTs described in this blog post are, unfortunately, a different animal, because once they are built, they can no longer be modified. As a result, the API has a split that distinguishes building an FST from querying an FST.
This split is reflected in the types exposed by the fst library. Among them are Set and SetBuilder, where the former is for querying and the latter is for insertion. Maps have a similar dichotomy with Map and MapBuilder.
Let us move on to a simple example that builds a set and writes it to a file. The really important property of this code is that the set is written to the file as it is being built. At no point is the entire set kept in memory!
(If you are not familiar with Rust, I have tried to be a bit verbose in the comments.)
build-set-file
// Imports the `File` type into this scope and the entire `std::io` module.
use std::fs::File;
use std::io;
// Imports the `SetBuilder` type from the `fst` module.
use fst::SetBuilder;
// Create a file handle that will write to "set.fst" in the current directory.
let file_handle = File::create("set.fst")?;
// Make sure writes to the file are buffered.
let buffered_writer = io::BufWriter::new(file_handle);
// Create a set builder that streams the data structure to set.fst.
// We could use a socket here, or an in memory buffer, or anything that
// is "writable" in Rust.
let mut set_builder = SetBuilder::new(buffered_writer)?;
// Insert a few keys from the greatest band of all time.
// An insert can fail in one of two ways: either a key was inserted out of
// order or there was a problem writing to the underlying file.
set_builder.insert("bruce")?;
set_builder.insert("clarence")?;
set_builder.insert("stevie")?;
// Finish building the set and make sure the entire data structure is flushed
// to disk. After this is called, no more inserts are allowed. (And indeed,
// are prevented by Rust's type/ownership system!)
set_builder.finish()?;
(If you are not familiar with Rust, you are probably wondering: what the heck is that ?? In short, it is an operator that uses early returns and polymorphism to handle errors for us. The best way to think about it is: every time you see a ?, it means that the underlying operation may fail, and if it does, return the error value and stop executing the current function. For more details, see my other blog post about error handling in Rust.
At a high level, this code:
Sometimes, however, we do not need to stream the set to a file on disk, or do not want to. Sometimes we just want to build it in memory and use it. That is possible too!
build-set-memory
use fst::{Set, SetBuilder};
// Create a set builder that streams the data structure to memory.
let mut set_builder = SetBuilder::memory();
// Inserts are the same as before.
// They can still fail if they are inserted out of order, but writes to the
// heap are (mostly) guaranteed to succeed. Since we know we're inserting these
// keys in the right order, we use "unwrap," which will panic or abort the
// current thread of execution if it fails.
set_builder.insert("bruce").unwrap();
set_builder.insert("clarence").unwrap();
set_builder.insert("stevie").unwrap();
// Finish building the set and get back a region of memory that can be
// read as an FST.
let fst_bytes = set_builder.into_inner()?;
// And create a new Set with those bytes.
// We'll cover this more in the next section on querying.
let set = Set::from_bytes(fst_bytes).unwrap();
This code is mostly the same as before, with two key differences:
Let us now look at the same process, but for maps. It is almost the same, except that now we insert values along with the keys:
build-map-memory
use fst::{Map, MapBuilder};
// Create a map builder that streams the data structure to memory.
let mut map_builder = MapBuilder::memory();
// Inserts are the same as before, except we include a value with each key.
map_builder.insert("bruce", 1972).unwrap();
map_builder.insert("clarence", 1972).unwrap();
map_builder.insert("stevie", 1975).unwrap();
// These steps are exactly the same as before.
let fst_bytes = map_builder.into_inner()?;
let map = Map::from_bytes(fst_bytes).unwrap();
That is almost all there is to building ordered sets or maps represented by FSTs. There is API documentation for both sets and maps.
Builder shortcut
In the examples above, we had to create a builder, insert the keys one by one, and finally call finish or into_inner before we could declare the process of building the set or map complete. This is often convenient in practice (for example, iterating over the lines in a file), but not so convenient for presenting short examples in a blog post. So let us take advantage of a small convenience.
The following code builds a set in memory:
build-set-shortcut
use fst::Set; let set = Set::from_iter(vec!["bruce", "clarence", "stevie"])?;
This produces the same result as before. The only difference is that we allocate a dynamically growing vector of elements before building the set, which is generally not recommended for large data.
The same trick works with maps, which take a sequence of tuples (keys and values) instead of a sequence of byte strings (keys):
build-map-shortcut
use fst::Map;
let map = Map::from_iter(vec![
("bruce", 1972),
("clarence", 1972),
("stevie", 1975),
])?;
Building an FST-based data structure is not exactly a convenient model. In particular, many operations can fail, especially when writing the data structure directly to a file. Consequently, building an FST-based data structure requires error handling.
Fortunately, this does not apply to queries. Once a set or map is built, we can fire off queries recklessly.
Sets are simple. The key operation is: "Does the set contain this key?"
query-set-contains
use fst::Set;
let set = Set::from_iter(vec!["bruce", "clarence", "stevie"])?;
assert!(set.contains("bruce")); // "bruce" is in the set
assert!(!set.contains("andrew")); // "andrew" is not
// Another obvious operation: how many elements are in the set?
assert_eq!(set.len(), 3);
Maps are again very similar, but we can also access the value associated with a key.
query-map-get
use fst::Map;
let map = Map::from_iter(vec![
("bruce", 1972),
("clarence", 1972),
("stevie", 1975),
])?;
// Maps have `contains_key`, which is just like a set's `contains`:
assert!(map.contains_key("bruce")); // "bruce" is in the map
assert!(!map.contains_key("andrew")); // "andrew" is not
// Maps also have `get`, which retrieves the value if it exists.
// `get` returns an `Option<u64>`, which is something that can either be
// empty (when the key does not exist) or present with the value.
assert_eq!(map.get("bruce"), Some(1972)); // bruce joined the band in 1972
assert_eq!(map.get("andrew"), None); // andrew was never in the band
Besides simple membership testing and key lookup, sets and maps also support iteration over their elements. These are ordered sets and maps, so iteration yields elements in the lexicographic order of the keys.
query-set-stream
use std::str::from_utf8; // converts UTF-8 bytes to a Rust string
// We import the usual `Set`, but also include `Streamer`, which is a trait
// that makes it possible to call `next` on a stream.
use fst::{Streamer, Set};
// Store the keys somewhere so that we can compare what we get with them and
// make sure they're the same.
let keys = vec!["bruce", "clarence", "danny", "garry", "max", "roy", "stevie"];
// Pass a reference with `&keys`. If we had just used `keys` instead, then it
// would have *moved* into `Set::from_iter`, which would prevent us from using
// it below to check that the keys we got are the same as the keys we gave.
let set = Set::from_iter(&keys)?;
// Ask the set for a stream of all of its keys.
let mut stream = set.stream();
// Iterate over the elements and collect them.
let mut got_keys = vec![];
while let Some(key) = stream.next() {
// Keys are byte sequences, but the keys we inserted are strings.
// Strings in Rust are UTF-8 encoded, so we need to decode here.
let key = from_utf8(key)?.to_string();
got_keys.push(key);
}
assert_eq!(keys, got_keys);
(If you are a Rustacean and wondering why on earth we use while let here instead of a for loop or an iterator adapter, it is time to let you in on a little dirty secret: the fst crate does not expose iterators. Instead, it provides streams. The technical rationale is explained in detail in the documentation for the Streamer trait.)
In this example we ask the set for a stream, which lets us iterate over all the keys in the set in order. The stream yields a reference to an internal buffer maintained by the stream. In Rust this is perfectly safe, because the type system will not let you call next on the stream while a reference to its internal buffer is still alive (at compile time). This means that you, as the consumer, can control whether all the keys are kept in memory (as in this example), or, if your task requires only a single pass over the data, you never need to allocate space for every key. This style of iteration is called streaming because ownership of the elements is tied to the iteration itself.
It is important to note that this is very different from other data structures such as BTreeSet. Namely, a tree data structure usually has a separate location allocated for each key, so it can simply return a reference to that allocation. That is, the ownership of the elements obtained from iteration is tied to the data structure. We cannot achieve this style of iteration with FST-based data structures without an unacceptable cost on every iteration. Namely, an FST does not store each key in its own location. Recall from the first part of this article that keys are stored in the transitions of the finite state machine. Consequently, keys are produced in the course of iteration.
All right, back to querying. Besides iterating over all the keys, we can also efficiently iterate over a subset of the keys using range queries. Here is an example building on the previous one.
query-set-range
// We now need the IntoStreamer trait, which provides a way to convert a
// range query into a stream.
use fst::{IntoStreamer, Streamer, Set};
// Same as previous example.
let keys = vec!["bruce", "clarence", "danny", "garry", "max", "roy", "stevie"];
let set = Set::from_iter(&keys)?;
// Build a range query that includes all keys greater than or equal to `c`
// and less than or equal to `roy`.
let range = set.range().ge("c").le("roy");
// Turn the range into a stream.
let stream = range.into_stream();
// Use a convenience method defined on streams to collect the elements in the
// stream into a sequence of strings. This is effectively a shorter form of the
// `while let` loop we wrote out in the previous example.
let got_keys = stream.into_strs()?;
// Check that we got the right keys.
assert_eq!(got_keys, &keys[1..6]);
The key line in the example above was this:
let range = set.range().ge("c").le("roy");
The range method returns a new range query, and the ge and le methods set the greater-than-or-equal and less-than-or-equal bounds, respectively. There are also gt and lt methods, which set the greater-than and less-than bounds, respectively. Any combination of these methods can be used (if one is used more than once, the last one replaces the earlier ones).
Once a range query is built, it can easily be turned into a stream:
let stream = range.into_stream();
Once we have a stream, we can iterate over it using the next method and a while let loop, as we saw in the previous example. In this example we instead called the into_strs method, which does the iteration and UTF-8 decoding for you, returning the results in a vector.
The same methods are available on maps, except that iteration yields tuples of keys and values instead of a single key.
Remember the first example, in which the SetBuilder streamed the data structure directly to a file? It turns out that this is a really important use case for FST-based data structures, especially because their driving force is huge collections of keys. Being able to write the data structure directly to disk as it is built, without keeping the entire data structure in memory, is a really nice convenience.
Can something similar be done for reading a set from disk? Of course, we can open a file, read its contents, and use them to build a Set:
read-set-mmap
use std::fs::File;
use std::io::Read;
use fst::Set;
// Open a handle to a file and read its entire contents into memory.
let mut file_handle = File::open("set.fst")?;
let mut bytes = vec![];
file_handle.read_to_end(&mut bytes)?;
// Construct the set.
let set = Set::from_bytes(bytes)?;
// Finally, we can query.
println!("number of elements: {}", set.len());
The expensive part of this code is reading the entire file into memory. The call to Set::from_bytes is actually quite fast. It reads a small piece of metadata encoded in the FST and computes a simple checksum. In fact, this process requires only 32 bytes!
One possible way to mitigate this is to teach the FST data structure to read directly from a file. In particular, it would know to perform seek system calls to move around the file in order to traverse the finite state machine. Unfortunately, this may be too expensive, because seek calls would happen very often. Each seek incurs system call overhead, which would probably make FST lookups excessively slow.
Another way to mitigate this is to maintain a size-bounded cache that keeps chunks of the file in memory, but probably not all of them. When a region of the file that is not in the cache needs to be accessed, the chunk of the file that includes that region is read and added to the cache (possibly evicting a chunk that has not been accessed for some time). When we access that region again and it is already in the cache, no I/O is required. This approach also lets us control what is kept in memory. Namely, we could make sure that all the chunks close to the machine's start state are in the cache, since in theory they will be accessed most often. Unfortunately, this approach is complex to implement and has other problems.
The third way is a so-called memory-mapped file. When a memory-mapped file is created, it is presented to us as if it were a sequence of bytes in memory. When we access that region of memory, it is possible that no actual data from the file is there yet to read. This triggers a page fault, which tells the operating system to read a chunk from the file and make it available in the sequence of bytes presented to the program. The operating system is then responsible for deciding which parts of the file are actually in memory. The actual process of reading data from the file and keeping it in memory is transparent to our program: all the fst crate sees is an ordinary sequence of bytes.
This third way is actually very similar to our idea above with the cache. The key difference is that the operating system manages the cache instead of us. This is a dramatic simplification in the implementation. Of course, there are certain costs. Because the operating system manages the cache, it cannot know that certain parts of the FST should always stay in memory. Therefore, we may sometimes not get optimal query time. These drawbacks can be somewhat mitigated by using calls such as mlock or madvise, which allow your process to tell the operating system that certain regions of the memory map should stay in or out of memory.
The fst crate supports the use of memory maps (but does not yet use mlock or madvise). Here is our previous example, modified to use a memory map:
read-set-file
use fst::Set;
// Construct the set from a file path. The fst crate implements this using a
// memory map, which is why this method is unsafe to call. Callers must ensure
// that they do not open another mutable memory map in the same program.
let set = unsafe { Set::from_path("set.fst")? };
// Finally, we can query. This can happen immediately, without having
// to read the entire set into memory.
println!("number of elements: {}", set.len());
That is all there is to it. The queries remain the same. The fact that a memory map is used is completely transparent to your program.
There is one more cost worth mentioning here. The format used to represent an FST in memory favors random access to the data. Namely, looking up a key may jump to different regions of the FST that are not close to each other at all. This means that reading an FST from disk through a memory map can be expensive, since random-access I/O is slow. This is especially true when using a non-solid-state disk, since random access will require many physical seeks. If you find yourself in such a situation, and the operating system's page cache cannot compensate for it, you may need to pay the cost up front and load the entire FST into memory. Note that this is not exactly a death sentence, since the goal of an FST is to be very small. For example, an FST with millions of keys can fit in a few megabytes of memory. (For example, all 3.
Given a set of strings, a very useful operation is fuzzy search. There are many different types of fuzzy search, but here we will look at only one: fuzzy search by Levenshtein, or "edit," distance.
Levenshtein distance is a way of comparing two strings. Namely, given strings A and B, the Levenshtein distance between A and B is the number of character insertions, deletions and substitutions needed to transform A into B. Here are some simple examples:
There are many ways to implement an algorithm that computes the Levenshtein distance between two strings. To a first approximation, the best that can be done is O(mn) time, where m and n are the lengths of the strings being compared.
For our purposes, the question we would like to answer is: does this key match any of the keys in the set with a Levenshtein distance of at most n?
Of course, we could implement an algorithm to compute the Levenshtein distance between two strings, iterate over the keys in one of our FST-based ordered sets, and run the algorithm on each key. If the distance between the query and the key is <= n, then we emit it as a match. Otherwise we skip the key and move on to the next one.
The problem with this approach is that it is incredibly slow. It requires running an effectively quadratic algorithm for every key in the set. Not good.
It turns out that for our particular use case we can do much better. Namely, in our case one of the strings in every distance computation for a single search is fixed: the query stays the same. Given these conditions and a known distance threshold, we can build an automaton that recognizes all strings matching our query.
Why is this useful? Well, our FST-based ordered set is an automaton! This means that answering the question with our ordered set is no different from intersecting two automata. This is really fast.
Here is a quick example demonstrating fuzzy search over an ordered set.
Levenshtein
// We've seen all these imports before except for Levenshtein.
// Levenshtein is a type that knows how to build Levenshtein automata.
use fst::{IntoStreamer, Streamer, Set};
use fst_levenshtein::Levenshtein;
let keys = vec!["fa", "fo", "fob", "focus", "foo", "food", "foul"];
let set = Set::from_iter(keys)?;
// Build our fuzzy query. This says to search for "foo" and return any keys
// that have a Levenshtein distance from "foo" of no more than 1.
let lev = Levenshtein::new("foo", 1)?;
// Apply our fuzzy query to the set we built and turn the query into a stream.
let stream = set.search(lev).into_stream();
// Get the results and confirm that they are what we expect.
let keys = stream.into_strs()?;
assert_eq!(keys, vec![
"fo", // 1 deletion
"fob", // 1 substitution
"foo", // 0 insertions/deletions/substitutions
"food", // 1 insertion
]);
A really important property of using an automaton to search our set is that it can efficiently rule out entire regions of our set. Namely, if our query is food with a distance threshold of 1, then it will never visit keys in the underlying FST with a length greater than exactly 5, because such keys can never match our search criteria. It can also skip many other keys, for example any keys that begin with two letters that are neither f nor o. Such keys can also never match our search criteria, because they already exceed the distance threshold.
Unfortunately, a discussion of exactly how Levenshtein automata are implemented is beyond the scope of this article. The implementation is partly based on ideas by Jules Jacobs. However, there is one part of this implementation worth talking about: Unicode.
In the previous section we saw a code example that builds a Levenshtein automaton, which can be used for fuzzy search of an ordered set or map in the fst crate.
A really important detail that we glossed over is how the Levenshtein distance is actually defined. Here is what I said, with emphasis added:
Levenshtein distance is a way of comparing two strings. Namely, given strings A and B, the Levenshtein distance between A and B is the number of character insertions, deletions and substitutions needed to transform A into B.
What is a "character," and how do our FST-based ordered sets and maps handle it? There is no single correct canonical definition of what a character is, so that was a poor choice of words for technical minds. A better word that reflects the actual implementation is the number of Unicode code points. That is, the Levenshtein distance is the number of insertions, deletions or substitutions of Unicode code points needed to transform one key into another.
Unfortunately, there is not enough room here to get into Unicode, but "An Introduction to Unicode" is informative reading that briefly defines the important terminology. David C. Zentgraf's write-up is also good, but much longer and more detailed. The important points are as follows:
Our choice to use codepoints is a natural compromise between correctness, implementation complexity and performance. The simplest approach would be to assume that every character is represented by a single byte. But what happens when a key contains ☃ (the Unicode snowman, which is a single codepoint), which is encoded as 3 bytes in UTF-8? The user sees it as a single character, but the Levenshtein automaton would treat it as 3 characters. That is bad.
Because our FSTs are really byte-based (that is, each transition in the transducer corresponds to exactly one byte), our Levenshtein automaton must have UTF-8 decoding built in . The implementation I wrote is based on a trick that Russ Cox used for RE2 (which, in turn, got it from Ken Thompson's grep). You can read more about it in the documentation of the utf8-ranges crate.
A really cool property that falls out of this approach is that if you run a Levenshtein query using this crate, then all keys are guaranteed to be valid UTF-8. If a key is not valid UTF-8, the Levenshtein automaton simply will not be able to match it.
Another type of query that we may want to run against our FST-based data structures is a regular expression . Simply put, a regular expression is a simple pattern syntax that describes regular languages. For example, the regular expression [0-9]+(foo|bar) matches any text that begins with one or more numeric digits followed by either foo or bar.
Of course, it would be nice to search our sets or maps using a regular expression. One way to do that is to iterate over all keys and apply the regular expression to each key. If there is no match, skip the key. Unfortunately, this would be quite slow. Rust's regular expressions do not slouch, but running a regular expression millions of times on small strings is bound to be slow. More importantly, with this approach we must visit every key in the set. For a large set, that could make a regular expression query infeasible.
As with computing the Levenshtein distance in the previous section, it turns out that we can do much better. Namely, since our regular expression stays the same throughout the search, we can precompute an automaton that knows how to match any text against the regular expression. Since our sets and maps are themselves automata, this means that we can search our data structures very efficiently by intersecting the two automata.
Here is a simple example:
regex
// We've seen all these imports before except for Regex.
// Regex is a type that knows how to build regular expression automata.
use fst::{IntoStreamer, Streamer, Set};
use fst_regex::Regex;
let keys = vec!["123", "food", "xyz123", "τροφή", "eda", "מזון", "☃☃☃"];
let set = Set::from_iter(keys)?;
// Build a regular expression. This can fail if the syntax is incorrect or
// if the automaton becomes too big.
// This particular regular expression matches keys that are not empty and
// only contain letters. Use of `\pL` here stands for "any Unicode codepoint
// that is considered a letter."
let lev = Regex::new(r"\pL+")?;
// Apply our regular expression query to the set we built and turn the query
// into a stream.
let stream = set.search(lev).into_stream();
// Get the results and confirm that they are what we expect.
let keys = stream.into_strs()?;
// Notice that "123", "xyz123" and "☃☃☃" did not match.
assert_eq!(keys, vec![
"food",
"τροφή",
"eda",
"מזון",
]);
In this example, we show how to run a regular expression query against an ordered set. The regular expression \pL+ will match only non-empty keys that consist of a sequence of UTF-8 encoded codepoints that are considered letters. Digits such as 2 and cool symbols such as ☃ (the Unicode snowman) are not considered letters, so keys containing these characters do not match our regular expression.
Regular expression queries have two important similarities to Levenshtein queries:
As with Levenshtein automata, we unfortunately will not discuss how the automaton is implemented. It is actually quite a big topic, and Russ Cox's series of articles on the subject is the authoritative source. It is also worth noting that the regex-syntax crate is what made this feasible. Thanks to it, we are guaranteed to use the same syntax as Rust's regex crate . (A regular expression parser is often one of the most complex aspects of an implementation!)
One last note: it is very easy to write a regular expression that takes a long time to match against a large set. For example, if a regular expression starts with .* (which means "match zero or more Unicode codepoints"), then it will likely end up visiting every key in the automaton.
The last thing we should talk about to complete the basic queries is set operations. The crate supports some common operations on fst sets: union, intersection, difference and symmetric difference. All of these operations can work efficiently on any number of sets or maps .
This is especially useful if you have several sets or maps on disk that you want to search. Since the fst crate supports memory-mapping them, this means we can search many sets almost instantly.
Let's look at an example that searches multiple FSTs and combines the search results into a single stream.
setop
use std::str::from_utf8;
use fst::{Streamer, Set};
use fst::set;
// Create 5 sets. As a convenience, these are stored in memory, but they could
// just as easily have been memory mapped from disk using `Set::from_path`.
let set1 = Set::from_iter(&["AC/DC", "Aerosmith"])?;
let set2 = Set::from_iter(&["Bob Seger", "Bruce Springsteen"])?;
let set3 = Set::from_iter(&["George Thorogood", "Golden Earring"])?;
let set4 = Set::from_iter(&["Kansas"])?;
let set5 = Set::from_iter(&["Metallica"])?;
// Build a set operation. All we need to do is add a stream from each set and
// ask for the union. (Other operations, such as `intersection`, are also
// available.)
let mut stream =
set::OpBuilder::new()
.add(&set1)
.add(&set2)
.add(&set3)
.add(&set4)
.add(&set5)
.union();
// Now collect all of the keys. `stream` is just like any other stream that
// we've seen before.
let mut keys = vec![];
while let Some(key) = stream.next() {
let key = from_utf8(key)?.to_string();
keys.push(key);
}
assert_eq!(keys, vec![
"AC/DC", "Aerosmith", "Bob Seger", "Bruce Springsteen",
"George Thorogood", "Golden Earring", "Kansas", "Metallica",
]);
In this example, 5 different sets are created in memory, a new set operation is created, a stream from each set is added to the builder, and then the union of all the streams is requested.
The union set operation, like all the others, is implemented in a streaming fashion. That is, none of the operations requires keeping all the keys in memory, precisely because the keys in each set are ordered. (The actual implementation uses a data structure called a binary heap .)
The great thing about streams is that they can be composed. In particular, it would be very sad if you were limited to taking the union of entire sets only. Instead, you can actually run any type of query over the sets and take the union.
Here is the same example as above, but with a regular expression that matches only keys with at least one space in them:
setop-regex
use std::str::from_utf8;
use fst::{Streamer, Set};
use fst::set;
use fst_regex::Regex;
// Create 5 sets. As a convenience, these are stored in memory, but they could
// just as easily have been memory mapped from disk using `Set::from_path`.
let set1 = Set::from_iter(&["AC/DC", "Aerosmith"])?;
let set2 = Set::from_iter(&["Bob Seger", "Bruce Springsteen"])?;
let set3 = Set::from_iter(&["George Thorogood", "Golden Earring"])?;
let set4 = Set::from_iter(&["Kansas"])?;
let set5 = Set::from_iter(&["Metallica"])?;
// Build our regular expression query.
let spaces = Regex::new(r".*\s.*")?;
// Build a set operation. All we need to do is add a stream from each set and
// ask for the union. (Other operations, such as `intersection`, are also
// available.)
let mut stream =
set::OpBuilder::new()
.add(set1.search(&spaces))
.add(set2.search(&spaces))
.add(set3.search(&spaces))
.add(set4.search(&spaces))
.add(set5.search(&spaces))
.union();
// This is the same as the previous example, except our search narrowed our
// results down a bit.
let mut keys = vec![];
while let Some(key) = stream.next() {
let key = from_utf8(key)?.to_string();
keys.push(key);
}
assert_eq!(keys, vec![
"Bob Seger", "Bruce Springsteen", "George Thorogood", "Golden Earring",
]);
Building a set operation works with any type of stream. Some streams may be regular expression queries, others Levenshtein queries, and still others range queries.
This section has covered sets, but we have not considered maps. Maps are somewhat more complicated, because the stream produced by a set operation over the keys of a map must also include the values associated with each key. In particular, for a union operation, each key emitted in the stream could have occurred in more than one of the given maps. I will refer you to the fst API documentation for map unions , which contains an example.
All the code examples we have seen so far have used the Set or Map data types in the fst crate. In fact, the implementation of Set or Map is not particularly interesting, since both simply wrap the Fst type. Indeed, their representation is:
// The Fst type is tucked away in the `raw` sub-module. use fst::raw::Fst; // These type declarations define sets and maps as nothing more than structs // with a single member: an Fst. pub struct Set(Fst); pub struct Map(Fst);
In other words, the Fst type is where all the action is. For the most part, building an Fst and querying it follow the same pattern as sets and maps. Here is an example:
FST builder
use fst::raw::{Builder, Fst, Output};
// The Fst type has a separate builder just like sets and maps.
let mut builder = Builder::memory();
builder.insert("bar", 1).unwrap();
builder.insert("baz", 2).unwrap();
builder.insert("foo", 3).unwrap();
// Finish construction and get the raw bytes of the fst.
let fst_bytes = builder.into_inner()?;
// Create an Fst that we can query.
let fst = Fst::from_bytes(fst_bytes)?;
// Basic querying.
assert!(fst.contains_key("foo"));
assert_eq!(fst.get("abc"), None);
// Looking up a value returns an `Output` instead of a `u64`.
// This is the internal representation of an output on a transition.
// The underlying u64 can be accessed with the `value` method.
assert_eq!(fst.get("baz"), Some(Output::new(2)));
// Methods like `stream`, `range` and `search` are also available, which
// function the same way as they do for sets and maps.
If you have been following along, this code should look mostly familiar by now. One key difference is that get returns an Output instead of a u64. Output is exposed because it is the internal representation of an output on a transition in the finite state transducer. If out is of type Output, you can get the underlying numeric value by calling out.value().
A key feature of the Fst type is access to the underlying finite state machine. Namely, two important methods are available on the Fst type:
Nodes provide the ability to walk over all of their transitions and to ask whether the node is a final state or not. For example, consider running a trace of the key baz through the machine:
FST node
use fst::raw::{Builder, Fst};
let mut builder = Builder::memory();
builder.insert("bar", 1).unwrap();
builder.insert("baz", 2).unwrap();
builder.insert("foo", 3).unwrap();
let fst_bytes = builder.into_inner()?;
let fst = Fst::from_bytes(fst_bytes)?;
// Get the root node of this FST.
let root = fst.root();
// Print the transitions out of the root node in lexicographic order.
// Outputs "b" followed by "f."
for transition in root.transitions() {
println!("{}", transition.inp as char);
}
// Find the position of a transition based on the input.
let i = root.find_input(b'b').unwrap();
// Get the transition.
let trans = root.transition(i);
// Get the node that the transition points to.
let node = fst.node(trans.addr);
// And so on...
With these tools, we can actually show how to implement the contains_key method!
FST contains
use fst::raw::Fst;
// The function takes a reference to an Fst and a key and returns true if
// and only if the key is in the Fst.
fn contains_key(fst: &Fst, key: &[u8]) -> bool {
// Start the search at the root node.
let mut node = fst.root();
// Iterate over every byte in the key.
for b in key {
// Look for a transition in this node for this byte.
match node.find_input(*b) {
// If one cannot be found, we can conclude that the key is not
// in this FST and quit early.
None => return false,
// Otherwise, we set the current node to the node that the found
// transition points to. In other words, we "advance" the finite
// state machine.
Some(i) => {
node = fst.node(node.transition_addr(i));
}
}
}
// After we've exhausted the key to look up, it is only in the FST if we
// ended at a final state.
node.is_final()
}
And that is pretty much all there is to it. The Node type has a few more useful documented methods that you may want to look through.
Comments