在前两节中，我一直小心避免谈论用于表示有序集或map的有限状态机的构造。也就是说，构造比简单的遍历要复杂一些。 In the previous two sections, I have been careful to avoid talking about the construction of finite state machines that are used to represent ordered sets or maps. Namely, construction is a bit more complex than simple traversal. 为了简单起见，我们对 set 或 map 中的元素进行了限制：它们必须按字典顺序添加。这是一个繁重的限制，但我们稍后会看到如何减轻它。 To keep things simple, we place a restriction on the elements in our set or map: they must be added in lexicographic order. This is an onerous restriction, but we will see later how to mitigate it....

fst库是"使用Automata和Rust索引1,600,000,000Keys"作者所建立的实现其博客思想的库。作者文章的后续就是针对其博客思想的构建历程，我们在这里先插入一下作者实现的这个库的一些主要功能，方便理解作者后续的思想。原文地址 fst是一个用于有效存储和搜索有序集合或者key是字符串的map的库。这个crate的一个关键设计目标是支持存储和搜索非常大的集合或map（即数十亿）。这意味着已经付出了很多努力来确保所有操作都是内存高效的。 fst is a library for efficiently storing and searching ordered sets or maps where the keys are byte strings. A key design goal of this crate is to support storing and searching very large sets or maps (i.e., billions). This means that much effort has gone in to making sure that all operations are memory efficient. 集合和映射由有限状态机(FSA)表示，它是一种对key中公共前缀和后缀的压缩形式。此外，有限状态机可以有效的对自动机（如正则表达式或模糊查询的Levenshtein距离）或字典范围进行查询。 Sets and maps are represented by a finite state machine, which acts as a form of compression on common prefixes and suffixes in the keys....

有序map(Ordered maps) 与有序集合一样，有序map类似于map，但在map的键上定义了顺序。就像集合一样，有序map通常使用二叉搜索树或btree实现，无序map通常使用哈希表实现。在我们的例子中，我们将看一个使用确定性非循环有限状态转换器的实现（缩写为 FST）。 As with ordered sets, an ordered map is like a map, but with an ordering defined on the keys of the map. Just like sets, ordered maps are typically implemented with a binary search tree or a btree, and unordered maps are typically implemented with a hash table. In our case, we will look at an implementation that uses a deterministic acyclic finite state transducer (abbreviated FST)....

原文链接 目录 (Table of Contents) 这篇文章很长，所以我整理了一个目录, 如果你想跳过某些内容。 This article is pretty long, so I’ve put together a table of contents in case you want to skip around. 第一部分讨论了有限状态机及其作为数据结构的抽象用途。本节旨在为您提供一个推理数据结构的思维模型。本节没有代码。 The first section discusses finite state machines and their use as data structures in the abstract. 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. 第二部分采用第一部分中开发的抽象，并用一个实现来演示它。本节主要是概述如何使用我的fst 库。本节包含代码。我们将讨论一些实现细节，但会避免过于混乱。如果您不关心代码而只想查看真实数据的实验，则可以跳过此部分。...

原文链接 事实证明，有限状态机对表达计算以外的其他事情很有用。有限状态机也可以用来紧凑地表示可以快速搜索的有序集合(Maps)或字符串映射(Sets)。 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. 在本文中，我将向您介绍有限状态机作为表示有序集合和映射的数据结构。这包括引入一个用 Rust 编写的实现，称为 fst crate。它带有完整的 API 文档。我还将向您展示如何使用简单的命令行工具构建它们。最后，我将讨论一些实验，最终从 2015 年 7 月的 Common Crawl Archive 中索引超过 1,600,000,000 个 URL（134 GB） In this article, I will teach you about finite state machines as a data structure for representing ordered sets and maps....