Lib.rs

有限状态转换器自动机。

转换器是一种自动机，它不仅接受或拒绝输入，还提供输出。虽然常规自动机检查输入字符串是否属于自动机接受的集合，但转换器将输入字符串映射到值。常规自动机类似于压缩的、不可变的集合，转换器则类似于压缩的、不可变的键值字典。通过共享输入字符串的前缀，字典树 压缩字符串集合或将字符串映射到值。自动机和转换器可以更好地压缩：它们可以共享前缀和后缀。由 Andrew Gallant（又名 burntsushi）撰写的 使用自动机和 Rust 指数 1,600,000,000 个键 是一篇优秀的入门介绍。

如果您正在寻找 Rust 中的通用转换器包，您可能正在寻找 fst 包。虽然这个实现完全通用且没有依赖项，但其功能集专门针对 peepmatic 的需求。

• 我们需要将额外的数据与每个状态相关联：评估下一个操作的匹配操作。

• 我们无法提前提供完整的输入字符串，因此此包必须支持增量查找。这是因为窥视孔优化器正在增量且动态地计算输入字符串：它查看当前状态的匹配操作，评估它，然后使用结果作为输入字符串的下一个字符。

• 我们还在构建转换器时支持增量插入和输出。这是必要的，因为我们不希望在成功匹配之前就发出绑定优化左侧模式（例如）的输出值，这可能直到我们达到第n个状态才发生。

• 我们需要支持通用的输出值。`fst` crate仅支持`u64`输出，而我们需要构建优化右侧的指令。

此实现基于Mihov和Maurel的《直接构造最小循环子序列转换器`。这意味着在构建过程中必须按字典顺序插入键。