Jiayun's Blog

📌 好文共赏 | Editor’s Pick

原文：Replacing a 3 GB SQLite database with a 10 MB FST (finite state transducer) binary 作者：Andrew Quinn（hiAndrewQuinn，Siilikuin 创始人，长期住芬兰的软件工程师 / 芬兰语爱好者） 发布：2026-05-10 阅读时长：约 12 分钟 多模评分：Opus 8.9 / Sonnet 8.7 / Gemini 8.8（综合 8.8/10） 一句话推荐：一位独立开发者用一个周末，把"差到能跑就行"的 3 GB SQLite + FTS 方案换成 10 MB 的静态 FST，300x 压缩比；但比数字更值得读的，是文章把 trie → DAFSA → FST 的演进、Finnish 黏着语形态学、以及"先做坏的简单事"的工程哲学，浓缩进 9000 字的一篇随笔里。

一、为什么值得读

如果你在 HN 上扫到标题"3 GB → 10 MB"，第一反应可能是又一篇 RIIR（Rewrite It In Rust）的炫技帖。但读完后会发现，Quinn 真正讲的是另一个更深的故事：在一个被"先上 SQLite/Postgres + FTS"训练过的工程世界里，我们已经默认遗忘了一整族 50 年前就被研究透的字符串数据结构——trie、DAFSA、minimal acyclic FSA、FST，每一层都比上一层更省内存，但代价是只支持只读、有序、静态的负载。

Quinn 的项目恰好就是这种负载：Taskusanakirja（芬兰语"口袋词典"）是一个静态打包的芬英双向词典，目标用户是"雅加达大学生从叔叔那继承的旧笔记本"。所有的查询都是只读，所有的数据在编译期就定下来。但因为芬兰语是黏着语，一个动词词干可以接出上百种变体（opiskelijassammekin = 学生 + 在内格 + 第一人称复数物主 + 也），naïve trie 最多塞 40 万词条到 50 MB；真正的全形态库需要 4000–6000 万词形，trie 直接爆掉，于是上一版只能"作弊"——单独打包一个 3 GB 的 SQLite + FTS 让用户额外下载。

文章的精彩之处有三层：

1. 数据结构层：把 trie 共享前缀、DAFSA/FSA 共享后缀、FST 同时共享前后缀这条压缩演化链讲透。读完你能解释为什么芬兰语词典特别适合 FST——因为成千上万个不同的词根，最终都共享同样十几条屈折后缀（-ssa-mme-kin、-lle-nne-kin），相当于一张"印钞许可证"。
2. 生态层：BurntSushi（ripgrep 作者）2015 年那篇 Index 1,600,000,000 Keys with Automata and Rust 的 fst crate，本来是为了索引 134 GB 的 Common Crawl URL 写的；十年后被一位独立开发者搬到一个完全不同的场景下使用，库的生命周期可以远比作者的预期长。
3. 工程哲学层：作者反复强调，能在一个周末做出 300x 压缩，前提是九个月前他选择了"做坏的简单事"——3 GB SQLite + FTS 当时就跑得通，用户用得开心；如果他当时坚持"先把最优解想清楚再开始"，可能至今连 v1 都没发布。这个观点叠在 v2 的优雅之上，比单纯炫技要立体得多。

文章不长（约 1500 词正文 + 五条信息密度极高的脚注），但每一个数字都是真的（zequals 取一位有效数字），每一个论点都有出处。它属于那种第一遍读觉得风趣，第二遍开始抄笔记，第三遍开始翻参考文献的好文。

二、核心观点深度解读

1. “Trie 一开始就够用”——为什么前缀树是 NLP 自动补全的默认选择

我们要解决的问题是 incremental search-as-you-type：用户每按一个键，从 N 万词条里实时返回前缀匹配。本科算法课都讲过：把字符串按字符摊开成多叉树，每一条从根到叶的路径就是一个词，任意前缀的所有后续 = 从某个内部节点开始的子树。这就是 trie。

Trie 的优势在 small-N 时显而易见：

• 查询时间和字符串长度成线性，与词库大小无关（不像哈希表，碰撞退化）。
• 共享前缀天然省空间——所有以 koira-（“狗”）开头的变体共用前 5 个节点。
• 实现简单到可以用 100 行 Go 写出来。

Quinn 的 v1 tsk 就靠 trie + “前 1–3 字符的查询结果预先 memoize” 把 40 万词条压到 50 MB 左右——足够嵌进一个静态链接的可执行文件里，单文件 distribute，没有 perceptible delay。这一步漂亮地证明了"做坏的简单事"的价值：用户拿到了能用的东西，市场告诉了你"是否值得做下一版"。

但 trie 有一个解不开的诅咒：它只共享前缀，不共享后缀。

原文：A trie shares prefixes (so kadun and kaduille share their first three nodes) but stores every distinct suffix path independently.

这就是 v1 撞墙的地方。当词条从 40 万扩到 4000 万时，重复的不是前缀，而是后缀和"中间段"。

2. 黏着语形态学是怎么把数据结构逼向极限的

这一节是文章里读起来最像语言学论文、但其实最关键的一段。芬兰语属于乌拉尔语系，是高度黏着语（agglutinative）：实词的形态变化不是"屈折"（像拉丁语 amō / amās / amat），而是把语法功能像贴纸一样一层层贴到词尾上：

1
2
3
4

opiskelija     学生（主格）
opiskelija + ssa     学生 + 在内格 ("在学生里")
opiskelija + ssa + mme  学生 + 在内格 + 我们的 ("在我们的学生里")
opiskelija + ssa + mme + kin  + 也 ("我们的学生里也")

Quinn 在脚注 2 里精确指出，一个芬兰语名词词干一共要乘以：“15 cases × 2 plurals × 6 possessives × N clitics”，最终一个词根可以爆出上百种合法形式。而且这些后缀不是简单拼接：根据"consonant gradation"（辅音弱化）和"vowel harmony"（元音和谐），katu（街道）的属格不是 katun 而是 kadun——t 因为音节闭合软化为 d。

原文：It simply has no way to share the cost of the thousands of words that all end in -ssa-mme-kin (“in our [X], as well”).

这句话点出了 trie 失败的本质：词库里几万个不同的词根，最终都会黏上同一组十几条屈折后缀。Trie 把每一条 -ssa-mme-kin 都当独立路径存了一遍，相当于把"the"重复抄了 4000 万次。

这才是 trie 在 4000–6000 万词形规模下爆炸的原因。问题不是"太多词"，而是"太多重复的尾巴"。

（这与我之前导读的 《Quack：DuckDB 在 2026 年从零设计一个数据库 wire 协议》 里讨论过的"针对静态、批处理负载重新设计专用结构"的思路在底层是同源的——通用关系数据库的全套机器（B-tree、MVCC、WAL）对静态只读字典完全是 overkill。）

3. 从 trie 到 DAFSA：把"重复的尾巴"折叠起来

Quinn 没有把数据结构课讲完整，但提到了关键的演化：Minimal acyclic deterministic finite-state automaton（MADFA），更常用的名字是 DAFSA（Directed Acyclic Finite-State Automaton）。HN 第一条评论一针见血：

“I was halfway through the article and began thinking that his described data structure sounded very familiar to something I used about 20 years ago. Sure enough, the first paragraph on the Wikipedia entry for DAFSA is: ‘DAFSA is the rediscovery of a data structure called Directed Acyclic …’”

DAFSA 和 trie 的差别只有一句话：trie 是树（每个节点最多一个父节点），DAFSA 是 DAG（可以有多个父节点指向同一子图）。换句话说，如果两个子树结构上完全一样（同样的转移、同样的接受状态），DAFSA 会把它们合并成同一个节点。

对芬兰语字典来说，这等价于：所有 -ssa-mme-kin 后缀路径只存一次，所有的词根尾端都指向那个共用子图的起点。这正是 trie 失去的那一半压缩——后缀共享。

构造 minimal DAFSA 的标准算法（Daciuk 等人 2000 年）非常优雅：把已排序的 key 流一条条加入，加入时维护一个"register"，每次完成一个分支就检查它的子图是否已存在于 register；若存在，就直接复用。整个过程 O(N) 时间、O(K) 内存（K = unique 子图数量），对 4000 万条芬兰语 inflection 几分钟跑完。

4. 再上一层：FST = DAFSA + 边权重

DAFSA 只能压缩"集合"——能告诉你某个字符串是否在词典里，但不能附加值（“这个词形对应哪个词根”、“它属于哪个屈折范式”）。FST（Finite-State Transducer）把"边"上挂上一个可累加的值，于是一条从起始状态走到接受状态的路径，不仅识别了一个字符串，还计算出一个数字或字符串作为输出。

BurntSushi 在 2015 年那篇里给的玩具例子最直观：

• 集合 { "feb", "jan" } → DAFSA 只需要识别。
• 映射 { "feb": 2, "jan": 1 } → FST 把 2 拆成 (2, 0, 0) 沿 feb 三个字符的边累加，把 1 拆成 (1, 0, 0) 沿 jan 累加。读到 feb 末尾时把路径上的 weight 加起来正好是 2。

对芬兰语字典而言：kadun -> katu 这种 inflection-to-lemma 映射，可以用 FST 把目标词根（或者其在 dictionary 中的整数 ID）作为 value 嵌进去。查询 kadun 就直接在常数时间内拿到 lemma，而不需要再做一次"反查表"。

这就是 BurntSushi/fst crate 的核心能力，也是 Quinn 选它的理由。当他把 SQLite 里那 4000 万 inflection → lemma 的映射 dump 出来、排序后 build 进 fst，整个 DAG 因为后缀共享 + 终止状态合并，压到 10 MB。300x。

5. 这套技术不是新发明——Lucene 用了十几年

Quinn 引用了 Mike McCandless 2010 年的博文：Lucene 的 inverted index 的 term dictionary 部分，从 4.0 开始就已经是 FST。每个 term（如 "obama"）作为 FST 的 key，把指向 posting list 的文件偏移量作为 value。整个 term dictionary 的内存占用因此能压到 GB 级 corpus 在 MB 级。

这就是为什么"3 GB → 10 MB"在搜索引擎工程师眼里其实并不惊人——他们已经用这套技术撑了十几年。反直觉的是：这套技术几乎没有传播到 SaaS/Web 工程的主流话语。当你问一个工程师"如何做静态字典的前缀查询"，回答通常是"丢进 Postgres pg_trgm 或 SQLite FTS 或 Algolia"。Trie 都很少有人写，更别说 FST。

Quinn 隐含的批评其实非常尖锐：我们正在丢失关于专用数据结构的工程素养。“先上数据库 + 通用索引"是默认答案，是教育的胜利，也是教育的失败——它确实让多数项目能在一周内 ship，但同时让本来能优雅解决的问题，永远停留在"3 GB 下载量是不是有点多"的讨论里。

（这点和我之前写的 《Redis 的野心代价》 里"一个’远程字典服务器’想成为一切，它就什么都不是"的批判恰好互补——一个讲通用工具的扩张代价，一个讲专用结构的失传成本。）

6. “做坏的简单事”——这才是文章真正的灵魂

如果只把它当一篇数据结构科普读，会错过 Quinn 真正想留下的那句话。脚注 5 是全文最长的：

原文（节选 / 自译）：“In the first quarter-century of my life… I could never overcome the guilt of not really knowing whether the tool I am building right now isn’t already superseded by some much better implementation someone else has already written 30 or 40 years ago… My central conceit is that this is a trap. You need to reinvent a couple of wheels to get to the edge of what we know about wheel-making, not a thousand wheels, and not zero.”

翻译成中文版的工程箴言大约是：你需要重新造几个轮子，才能走到"造轮子"知识的边缘——不是几千个轮子，也不是零个。

这是非常 Caplanian（取自 Bryan Caplan 的教育经济学）的观点：技能不是听课听出来的，是做出来的；但"做"也不是从零自虐，而是在你已经有点 sense 的领域，刻意挑选几个看起来"已被解决"的问题重做一遍。这个过程会把你推到那个领域的"已知前沿”，而那里恰好是新工具诞生的地方。

Quinn 的 v1 → v2 演化是一个具体的案例：v1 是"做坏的简单事"，用 SQLite + FTS 把产品 ship 出去；v2 是"九个月后回头重做一次"，这次他已经积累了足够的 Rust 经验、足够的 FST 知识、以及足够的产品反馈来知道"哪些功能其实可以砍"。这两步合起来，才是真正的工程方法论。如果他一开始就立志做 v2 那样的优雅版，他大概率永远做不出来。

这一点对当下 AI 编程时代尤其重要——当 LLM 让"做坏的简单事"成本进一步降低，真正稀缺的，反而是知道何时回头"解决一次"的判断力。这点与我前几天导读的 《资深开发者为何"说不清"自己的价值：Speed 与 Scale 的两个循环》 有强烈的呼应——senior 工程师卖的就是这种"何时该切换 mode"的元判断。

7. FST 的代价：什么是它做不到的

Quinn 在文章里点到、但没展开的一条：FST 的两大局限。

第一是构建必须有序。FST 的 minimal 化算法假设 key 流是已排序的，加入新 key 时只能比上一个 key 大。这意味着插入式更新基本不可能——任何"加一个词"的操作都要重建整个 FST。所以它只适合 batch 构建 + 长期只读的场景。

第二是 value 类型受限。weight 必须支持某种"幺半群"（monoid）运算，最常见的是 u64 的加法或 min/max。如果你想把任意 JSON 当 value 挂上去，需要绕一层——通常是把 JSON 序列化进一个 side car 文件，FST 只存偏移量。

对 Quinn 的字典场景，这两个限制都不重要：词库只在编译期更新，value 是 lemma 的整数 ID，完美契合。但这也解释了为什么 FST 没有"杀掉" SQLite——大多数实际系统都需要在线更新和复杂 value，于是被迫接受 B-tree 的开销。这是工程上一个非常具体的"无银弹"案例。

8. 为什么 Rust 在这里恰好是对的

文章的副标题虽然是"Had I considered rewriting it in Rust"的自嘲，但 Rust 在这里的选择并不偶然。三个理由叠加：

1. BurntSushi/fst 是 Rust 生态独有的成熟实现。Python 有 marisa-trie、Java 有 Lucene 内置，但带 streaming API + Levenshtein automaton + 正则匹配 + 集合运算的 FST，目前还是 fst crate 最完整。这是一个 Rust 把"系统级数据结构 + 函数式接口"的两边吃透的领域。
2. memory-mapped 二进制是默认范式。FST 文件可以直接 mmap 进进程，不需要反序列化。Rust 的零拷贝 + bytemuck 风格让这种"文件即内存结构"的模式异常顺手。
3. 静态链接 + 跨平台单二进制。Quinn 的产品要 ship 给"印尼大学生的旧笔记本"，意味着 Windows / macOS / Linux 三平台 + 不依赖 libc 升级。Rust 的 --target x86_64-unknown-linux-musl 是这个场景的几乎唯一答案。

这恰好是 kerkour 那篇 《The limits of Rust》里反复强调的"Rust 真正闪光的地方"：跨平台 common core + 系统编程 + 性能敏感的库。Quinn 的项目就坐在这个三角形的正中心。

三、延伸阅读图谱

作者其他代表作

1. The highest personal ROI program I have written so far：早期 finstem 的故事，讲 fzf + 个人词汇表如何成为他学芬兰语的核心工具。tsk 项目的起源。
2. You don’t need cgo to use SQLite in your Go binary：v1 时代的工程笔记，讲如何把 SQLite 用 modernc.org/sqlite 纯 Go 实现塞进单文件。“做坏的简单事"的具体写法。
3. Cross-platform TUIs are easier than cross-platform GUIs：为什么 tsk 一开始就坚持 TUI——为了避免 GUI 跨平台的地狱。
4. Digital resiliency 2025 - my first self-audit：长达 72 分钟阅读时长的个人数字主权审计。和 monokai 那篇"搬到欧洲"互补。
5. We should use prediction markets for long term software maintenance：他对 OSS 长期维护的另类构想。

必读的祖文与同主题

1. Index 1,600,000,000 Keys with Automata and Rust — BurntSushi 2015 年的那篇祖父级文章。8000 字 + 大量交互示例。如果你想真正理解 FST 是什么，这一篇是绕不开的圣经。
2. Using Finite State Transducers in Lucene — Mike McCandless 讲 Lucene 4.0 为什么把 term dictionary 换成 FST。工业界的最经典 case study。
3. Incremental Construction of Minimal Acyclic Finite-State Automata — Daciuk et al. 2000，FST 构造算法的原始论文。如果你想自己实现一份 FST 而不是用 fst crate。
4. Are We Learning Yet? 与 crates.io fst — Rust 数据结构生态地图。fst 的下载数据揭示它的"沉默基础设施"地位。
5. Marisa-trie: a static trie data structure that fits in 1/2 to 1/4 of LOUDS Patricia trie — 另一条压缩 trie 路线，C++ 写的，Python 有绑定。和 FST 的设计选择不同但目标一致。

反方观点与张力

1. “Just use SQLite FTS” — HN 评论里有人质疑：常规 gzip 压缩 3 GB 数据可能也能拿到 10x 缩小，为什么非要 FST？Quinn 没正面回答，但答案隐藏在 latency 里：FST 支持 mmap + 常数时间前缀/模糊查询，gzip 数据需要先解压。
2. Why I do not use Rust for embedded — 系统编程社区里 Rust 反方常被引用的一篇。讲学习曲线和 toolchain 摩擦。
3. Programming languages should be platforms, not products — kerkour 这周另一篇文章，反 Rust 升级节奏。和 Quinn 这种"挑成熟点的 Rust 库用"的实用主义构成有趣对比。

四、编辑延伸思考：数据结构的"沉默基础设施"问题

读完 Quinn 这篇，我一直在想一个更大的问题：为什么 FST 这种 50 年前就被研究透、Lucene 用了 15 年、ripgrep 作者写过 8000 字博文的数据结构，会在大多数应用工程师的视野里"消失”？

我的判断是：这是**“垂直整合 vs 横向解耦"两种工程文化交锋的副作用**。

过去二十年，软件行业的胜利者是"横向解耦派”：把数据存到 Postgres，搜索丢给 Elasticsearch / Algolia，缓存上 Redis，所有人通过通用的"NoSQL / SQL / KV / FTS"接口对话。这套架构的胜利不是因为它技术上最优，而是因为它让协作成本足够低——你换一个工程师，他无需理解你的具体数据形态，只要会用 Postgres 的就能上手。但代价是：每一层都为通用性付出 10–100x 的存储和延迟代价，因为通用接口必然要支撑插入、删除、并发、事务、范围查询、模糊匹配等所有可能的访问模式。

FST 属于另一种文化：垂直整合派。它假设你的数据是静态的、有序的、批构建一次后只读的；它假设你愿意花时间想清楚 value 的语义、key 的分布、查询的形态。一旦这些假设满足，它能给你 10–1000x 的省。但它不能在团队里横向传播——你不能跟产品经理说"我们的字典是 FST"，因为他们听不懂；你也不能让一个 7 天后接手的人在不读 BurntSushi 博文的情况下维护它。

这两种文化都对，但目前的工程教育和招聘市场严重偏向第一种。结果是：

• 每个团队都默认 throw money 给云存储（Postgres 的 3 GB 比 FST 的 10 MB 多花 300 倍空间，但没人在 sprint 里 push 这个问题）。
• 真正的数据结构知识沉淀在少数"基础设施部门"和开源作者手里（BurntSushi、Cap’n Proto 的作者 kentonv、Datomic/XTDB 那批人）。
• 当一个独立开发者像 Quinn 这样"重新发现"它，社区会爆出一种半惊讶半怀旧的反应——这就是为什么这篇文章在 HN 拿了 191 分、Lobsters 101 分：很多人内心其实知道有更好的方法，只是已经默认放弃了。

更尖锐的问题：AI 编程时代，这种知识会更稀缺还是更普及？

乐观看，LLM 让"哪些场景该用 FST"的检索成本降到零——Claude / GPT-5.5 都能瞬间告诉你 fst crate 存在。悲观看，“AI 帮你 ship"的最低成本路径仍然是"丢进数据库”——LLM 默认推荐的方案永远是"通用、能跑、低风险的"，而垂直定制的优雅方案需要工程师主动问出特定问题才能被引导出来。

Quinn 这篇文章给的答案我倾向于乐观，但有一个前提：你必须把’重新发明几个轮子’当作终身策略而非临时项目。LLM 提供了关于轮子的全部说明书，但你需要亲手造过几个轮子，才会在新场景下记得问"这次能不能换种轮子"。

（这点与 《教会 Claude"为什么"》 里"传授原则比演示动作更高效"的思想是同一枚硬币的两面——人也好，模型也好，深度泛化都来自原理理解，而非样本记忆。）

最后一条编辑感想：Quinn 项目的目标用户是"印尼大学生从叔叔那继承的旧笔记本"。这句话像一个温柔的反抗：在每周都有新框架号称"对你的 32-core M5 Max 优化过"的 2026 年，给十年前的硬件做精致的软件，可能是当前对工程伦理最强的表达之一。10 MB 的二进制不是炫技，它是关于"谁应该被服务"的政治选择。

五、配套资料导览

为方便深读，本文配套了：

• mindmap.svg：从 trie → DAFSA → FST 的演化树状图。
• concept-cards.md：10 张关键概念卡片（trie、DAFSA、FST、minimal acyclic automaton、Levenshtein automaton、agglutinative language、Daciuk algorithm、suffix sharing、mmap-as-deserialization、zequals method）。
• glossary.md：30 条英中对照术语表，覆盖数据结构 + 形态学双侧词汇。
• cover.svg：深色封面图。

六、谁应该读

• 正在维护"静态字典 / 词库 / 路由表 / 资产表"的工程师：你可能已经在 SQLite + FTS 上撑了几年；FST 可能是你下一个 2 周项目的最大杠杆。
• 搜索引擎、IDE 自动补全、CLI 工具作者：trie / DAFSA / FST 的三层迭代是这个领域的基本功，错过任何一层都会让你的产品在某个 scale 处碰墙。
• NLP / 语言学 / 输入法工程师：黏着语形态学 + suffix-sharing 数据结构是一个被严重 underrated 的交叉学科领域。
• 任何相信"重新造几个轮子"哲学的工程师：Quinn 的脚注 5 单独印出来都值得贴在墙上。

如果你最近一年只读一篇关于数据结构的文章，让它是这一篇加上 BurntSushi 那篇祖文。这两篇配合阅读，比绝大多数 600 页的算法教科书更能让你理解"为什么有些工程师的代码就是比别人 100 倍小、100 倍快"。

导读编辑：xiejiayun 评审过程：Opus 主评 8.9 + Sonnet 8.7 + Gemini 8.8 = 综合 8.8/10，符合发表标准。 版权声明：本文为对 Andrew Quinn 原文的导读与延伸思考，所有引用均不超过 3 句，总引用量不超过原文 8%。配图与代码示例均为本文重绘 / 重写。