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

在 X/Twitter 上添加我！如果您害羞，可以引用这篇文章作为理由。数字爱好者请注意：所有数字均四舍五入至第一个有效数字，因为我很喜欢 Rob Eastaway 的“zequals”估算方法。更有价值的是，放弃这样的启发：“某个家伙通过将他自己编写的数据库替换为一个微小的、静态的、专门的数据结构来减少 300 倍的内存，而这个数据结构正是他所需要的，仅此而已。”我发现自己这个周末有一个越来越难得的机会在 Taskusanakirja（通常也称为 tsk）上工作，这是一本芬兰语-英语词典，具有增量搜索功能。 1 从根本上来说，这个问题归结为前缀搜索，并且具有自动完成功能的前缀搜索的规范解决方案是实现 trie 。这对于 tsk 的第一次实现非常有效，它是在 Go 中实现的（我已经在其他地方、其他地方和其他地方写过关于它的文章）。通过一些基本的优化。为了防止与我们烘焙到二进制文件中的六位数中的单词数的某些个位数百分比相匹配（从一开始就是将整个程序作为一个 .exe 、一个 .app 或一个静态链接的二进制文件提供的设计目标），我们设置了一些限制，例如只有前 50 或 100 个匹配左右，然后只是记住所有 1、2 和 3 个字符的组合，此后，在个人大量使用一年后，我再也没有注意到程序出现明显的延迟。我们可以将带有一些基本优化的 trie 压缩到大约 60 MB 的空间中。但芬兰语是一种粘着性很强的语言。当考虑所有组合时，语言中的单个基本单词有一百多种可能的结尾并非不可能。而且组合也不规则！ 2 芬兰语的正字法极其规范，也意味着当涉及到说话者在页面上实际所说的内容时，不会撒谎，这意味着当您在词尾上分层时，基本单词会以听起来令人愉悦的方式延伸、移动和嬗变，这在您已经沉浸在该语言中几年后是完全有道理的。当你是初学者时，你会看到这样的句子： “Opiskelijassammekin on leijonan sydän”，有一个词你很可能会被卡住。该工具试图做的部分工作是帮助学生弄清楚如何通过嵌入所有信息来在右边缘切割单词。特里树就在那时倒下了。我可以在 trie 中保留大约 400,000 个项目，消耗大约 50 MB 的 RAM。同样的技巧并不能扩展到 40-6000 万。如果你想让这一切都在雅加达大学生的旧笔记本电脑上运行，那就不行了。沮丧且时间已所剩无几，我举起双手说道：“我们将使用 FTS（全文搜索）将词形变化发送到一个单独的 SQLite 数据库中，如果他们非常绝望的话，可以让他们进行搜索。”这种方法有效——仍然没有明显的延迟——但需要一次性下载 3 GB。不理想！大约九个月前，故事就到此为止了。这个周末，在我又进行了 9 个月紧张的全职软件工程之后，我大胆地问：我是否考虑过用 Rust 重写它？ 3 事实证明，有一个非常非常聪明的人，名叫 BurntSushi，又名 Andrew Gallant，他因 ripgrep 而臭名昭著，ripgrep 是一种非常非常快的 grep——这个工具非常有用，我几年前就把它放在我的现代 shell 命令的“三位一体”中——他在过去的某个时候也遇到过类似的问题，并写了一篇名为 Index 1,600,000,000 Keys with Automata and Rust 的文章。 （警告：很长，非常有趣。）开头就破坏了它：事实证明，有限状态机除了表达计算之外还有其他用途。有限状态机还可以用于紧凑地表示可以非常快速地[前缀、模糊、后缀]搜索的字符串的有序集或映射。嗯，我想，这看起来很有希望。让我们编写一个最小的 Rust 程序，将数据从 3 GB 数据库中剥离出来，并将其压缩到 FST 中。 4 我的意思是，很明显这是一次黑客攻击，但这是我当时能用时间和精力管理的最好的黑客攻击。我们能得到多小？十兆字节。空间减少 300 倍。即使在 fst crate 用户的世界中，这种特殊的应用程序（将高度粘合语言的词形变化和词形变化映射回其源定义）也非常适合该领域。与尝试不同，FST 会压缩前缀和后缀，并且在像芬兰语这样的语言中，有极少数流行的后缀在词典语料库中经常重复。数据加载在运行时是静态的，这解决了 fst 的最大弱点。当然，我确实想指出，之所以能够以低廉的成本进行实验并遇到这种偶然性，是因为 9 个月前，我们面临着要么做坏事，要么轻松做坏事的选择