用 10 MB 的 FST（有限状态转换器）二进制文件替换 3 GB 的 SQLite 数据库

# 用 10 MB 的 FST（有限状态转换器）二进制文件替换 3 GB 的 SQLite 数据库 来源：https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/ *注：献给数学爱好者（https://www.youtube.com/watch?v=aOJOfh2_4PE）：所有数字都已舍入到第一位有效数字，因为我是 Rob Eastaway 的“近似相等”（zequals）方法（https://robeastaway.com/blog/introducing-zequals）的粉丝，这种方法在估算时能直奔主题。带走这一启发式结论要更有价值得多：“某个家伙通过用一种微小、静态、专门化的数据结构替换他临时拼凑的数据库，实现了 300 倍的内存缩减，该数据结构刚好满足他的需求，不多也不少”。* 这个周末，我难得地有机会继续开发 Taskusanakirja（https://taskusanakirja.com/），也就是常说的 `tsk`，这是一个带有增量“随输入即搜”功能的芬兰语-英语词典。1 (https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/#fn:1) 从根本上说，这个问题可以归结为前缀搜索（https://en.wikipedia.org/wiki/Trie），而带有自动补全功能的前缀搜索的标准解决方案是实现一棵前缀树（Trie）（https://www.baeldung.com/cs/tries-prefix-trees）。 对于 `tsk` 的第一版实现（是用 Go 写的，我曾在别处（https://til.andrew-quinn.me/posts/you-don-t-need-cgo-to-use-sqlite-in-your-go-binary/）、别处（https://til.andrew-quinn.me/posts/cross-platform-tuis-are-easier-than-cross-platform-guis/）和别处（https://til.andrew-quinn.me/posts/the-highest-personal-roi-program-i-have-written-so-far/）写过），这种方法运行得非常完美。配合一些基础优化，为了防止在二进制文件中烘焙的数十万单词中有极少数（个位数百分比）的单词被匹配到（从一开始的设计目标就是将整个程序打包为*单个* `.exe`、*单个* `.app` 或*单个*静态链接的二进制文件），我们设定了一些限制，例如只匹配前 50 或 100 个左右的结果，并将所有 1、2 和 3 个字符的组合进行记忆化存储。在此之后，经过一年的重度个人使用，我从未再察觉到程序有明显延迟。通过这类基本优化，我们勉强可以将 Trie 压缩到约 60 MB 的空间。 但芬兰语是一种高度黏着语（https://en.wikipedia.org/wiki/Agglutinative_language）。考虑到所有组合，一个基本单词拥有超过一百种可能的词尾结尾并非不可能。而且这些组合并不规则。2 芬兰语极其规范的正字法*也*意味着书面语如实反映了说话者的实际发音，这意味着当你层层叠加词尾时，基本单词会在发音上以悦耳的方式拉伸、移动和变形，在你已经沉浸在该语言环境中一两年后，这完全合乎逻辑。但当你还是个初学者，看到类似“Opiskelijassammekin on leijonan sydän”这样的句子时，你很可能会在一个词上卡住。这个工具试图做的一部分工作，就是帮助学生通过在嵌入的信息中展示如何在正确的边界*拆分*单词来解决问题。 到了这一步，Trie 方法就不管用了。我可以在 Trie 中存放约 40 万个条目，占用约 50 MB 的 RAM。同样的技巧无法扩展到 4000 万到 6000 万条记录。如果你希望它能在雅加达某大学学生的旧笔记本电脑上运行，就更不可能了。沮丧且时间紧迫的我摊开双手说：“我们将变位词放在一个单独的 SQLite 数据库中，支持全文搜索（FTS），如果他们实在着急，就让他们在那上面搜吧。”这*行得通*——依然没有可察觉的延迟——但这需要一次性下载 3 GB 的数据。并不理想！ 故事就到这里，大概 9 个月前。这个周末，在经历了又 9 个月的全职高强度软件工程工作后，我大胆地自问：我是否考虑过用 Rust 重写它？（https://transitiontech.ca/random/RIIR）3 (https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/#fn:3) 事实证明，有一位*非常、非常*聪明的家伙，名叫 BurntSushi（即 Andrew Gallant）（https://github.com/BurntSushi），因 `ripgrep` 而闻名，这是一个超级快的 grep 工具（https://github.com/BurntSushi/ripgrep）——一个如此普遍有用的工具，以至于我多年前就把它列入了现代 Shell 命令的“神圣三位一体”（https://github.com/hiAndrewQuinn/shell-bling-ubuntu#the-holy-trinity）。他*也*在过去某个时刻面临过类似的问题，并写了一篇名为《使用自动机和 Rust 索引 16 亿个键》（Index 1,600,000,000 Keys with Automata and Rust）（https://burntsushi.net/transducers/）的文章。（警告：文章很长，但极其有趣。）开篇就剧透了： > 事实证明，有限状态机除了表达计算外，还有别的用处。有限状态机还可以用于紧凑地表示有序字符串集合或映射，并能非常快速地进行\[前缀、模糊、后缀\]搜索。 我想，这看起来很有希望。让我们写一个最小的 Rust 程序，从那 3 GB 的数据库中提取数据，并将其压缩成这种叫 FST 的东西之一。4 (https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/#fn:4) 我的意思是，这显然一直是个临时凑合的方案，但那是当时在时间和精力有限情况下我能做到的最好方案。我们能把它压缩得多小？ **10 _兆_字节。**空间缩减了 300 倍。即使在 `fst` 库（https://docs.rs/fst/）用户的世界里，这个特定应用——将一种高度黏着语言的变位和变格映射回其原始定义——也非常适合该领域。与 Trie 不同，FST 同时压缩*前缀*和*后缀*，而在芬兰语这样的语言中，字典语料库中重复使用极其频繁的流行后缀只有极少数几个。数据负载在运行时是静态的，这避开了 `fst` 最大的弱点。 当然，我必须指出，之所以能够低成本地进行实验并偶然发现这一巧合，是因为 9 个月前，面对做“糟糕但容易的事”还是“正确但一事无成”的选择时，我选择了做那个糟糕但容易的事。5 (https://til.andrew-quinn.me/posts/replacing-a-3-gb-sqlite-database-with-a-7-mb-fst-finite-state-trandsucer-binary/#fn:5) SQLite 数据库*管用*！我*理解*它的后台运作方式，包括它的 B 树和全文搜索扩展（https://www.sqlite.org/fts5.html）。我想我甚至曾用过那个相同的 FTS 扩展来支持某些使用率较低的功能，这些功能*不*在 `tsk v2.0.0` 目前的 alpha 版本中，如果意味着要牺牲现在这种令人垂涎的内存占用，很可能会被完全砍掉。 因为 `v2` 的专业版最终体积约为 20 MB，包含所有功能，这比 `v1` 免费版的体积还要小 3 倍。让我们看看最终哪些功能能熬过剪辑室的考验。