从 3 GB 到 10 MB：使用有限状态转换器优化前缀搜索

当构建“边输入边搜索”的词典时，主要的挑战在于高效的前缀搜索。对于大多数开发者来说，首选方案是 trie（前缀树），它通过共享公共前缀来实现快速查找。然而，随着数据集的增长——特别是在处理黏着语（agglutinative languages）复杂的形态学时——即使是经过优化的 trie 也会变得庞大到难以承受。

在最近一个名为 Taskusanakirja (tsk) 的芬兰语-英语词典项目中，作者面临了这种规模化的瓶颈。最初一个易于管理的 Go 实现，最终需要一个 3 GB 的 SQLite 数据库来处理数百万个屈折词形。解决方案是什么？迁移到 Rust 并实现有限状态转换器（Finite State Transducer, FST）。

挑战：黏着语的复杂性

芬兰语是一种高度黏着性的语言，这意味着它通过在词根上添加多个后缀来构建单词。一个基础词可以拥有超过一百种可能的结尾。这种复杂性由于“辅音梯度”和“元音和谐”而进一步加剧，即随着后缀的添加，单词本身的词根也会发生偏移和转变。

对于语言学习者来说，能够搜索特定的屈折形式并找到其词根是至关重要的。然而，这会导致数据爆炸：

  • Trie 在大规模应用时会失效： 虽然 trie 可以高效地在 ~50 MB 的 RAM 中存储 400,000 个条目，但它无法在不消耗数 GB 内存的情况下扩展到 4000 万至 6000 万个条目。
  • “笨拙但简单”的方案： 为了让项目继续推进，作者最初实现了一个带有全文搜索（FTS）功能的 SQLite 数据库。虽然功能上性能良好，但它需要用户下载 3 GB 的数据——这与“轻量级口袋词典”的目标相去甚远。

解决方案：有限状态转换器 (FST)

为了解决内存危机，作者转向了 Rust 中的 fst crate，其灵感来源于 Andrew Gallant (BurntSushi) 的工作。

虽然 trie 仅共享前缀，但有限状态转换器（具体来说是最小化无环确定性有限状态自动机）同时共享前缀和后缀。

为什么 FST 适用于芬兰语

在芬兰语这样的语言中，成千上万个不同的单词通常共享相同的几种热门屈折模式（例如，结尾如 -ssa-mme-kin）。在标准的 trie 中，每个后缀实例都会被存储为一条独立的路径。而在 FST 中，任何结构上完全相同的子树都会被合并。

这种“后缀共享”极大地提高了内存效率。通过使用 FST 将变位和变格映射回其原始定义，作者将数据占用从 3 GB (SQLite) 减少到了仅 10 MB——实现了 300 倍的缩减。

工程经验：从“天真”开始的价值

这次优化之旅中最深刻的感悟之一是“把问题解决两次”的哲学。作者认为，从一个“笨拙但简单”的方案（如 SQLite DB）开始，通常优于从一开始就花费数周时间研究完美的架构。

"SQLite 数据库可以工作！我理解它的工作原理……我认为把问题解决两次是可以的。"

这种方法具有几个优势：

  1. 即时验证： 你证明了该功能是可行且有用的。
  2. 参考实现： 天真的版本可以作为衡量标准，用于验证高度优化版本的正确性。
  3. 降低风险： 你避免了“分析瘫痪”，并确保项目能够实际交付。

更广泛的应用

FST 在此背景下的成功并不局限于芬兰语。正如社区讨论中所提到的，类似的技术非常适用于其他黏着语，如土耳其语或日语，其中单词的形成遵循类似的“词根+后缀”分层模式。

此外，所描述的数据结构与有向无环词图 (DAWG) 非常接近，这是一种在过去几十年中被重新发现的各种形式的结构，专门用于解决此类词典压缩问题。

转换总结

| 指标 | 初始 Go/Trie | 中间阶段 SQLite | 最终 Rust/FST | | :--- | :--- |" | 3 GB | 10 MB | | 搜索类型 | 前缀 | 全文搜索 | 前缀/模糊/后缀 | | 可移植性 | 高 | 中 (外部数据库) | 非常高 (静态二进制文件) |

Sources