DEV Community
·
我们如何用Rust为130万词构建300微秒拼写纠正系统
💡
原文英文，约1300词，阅读约需5分钟。
📝
内容提要
我们推出了Hacker News搜索和RAG引擎，速度比第一版快100倍，拼写纠正系统对正确拼写的查询只需300微秒，拼写错误的查询每个单词大约需要5毫秒。本文解释了实现这一目标的方法。
🎯
关键要点
- 推出了Hacker News搜索和RAG引擎，拼写纠正系统速度比第一版快100倍。
- 正确拼写的查询响应时间为300微秒，拼写错误的查询每个单词约需5毫秒。
- 为构建字典，使用了两个不同的工作者，一个用于从数据库中提取文档，另一个用于处理和存储单词。
- 选择ClickHouse存储字典，以解决Postgres写入时的死锁和性能问题。
- 使用BKTree数据结构进行拼写纠正，构建每个数据集的BKTrees以提高查询效率。
- 在API服务器上优化拼写纠正逻辑，将正确拼写查询的时间降低到约300微秒。
- 维护一个包含约400,000个英语单词的哈希集，以防止对合法单词的错误纠正。
- 通过前缀和后缀分析来识别单词，构建Trie树以查找匹配的前缀和后缀。
- 对不在字典中的单词进行BKTree搜索，生成候选纠正词。
- 使用评分算法从候选纠正词中选择最佳纠正，优先考虑前缀匹配和词频。
- 未来计划利用相同系统实现查询拆分和连接，以提高相关性。
❓
延伸问答
这个拼写纠正系统的响应时间是多少？
正确拼写的查询响应时间为300微秒，拼写错误的查询每个单词约需5毫秒。
为什么选择ClickHouse来存储字典？
选择ClickHouse是因为在Postgres写入时遇到死锁和性能问题，ClickHouse的异步插入非常适合此任务。
BKTree数据结构在拼写纠正中有什么作用？
BKTree用于高效比较查询中的单词和字典中的单词，能够在O(log N)时间复杂度内进行拼写纠正。
如何识别不在字典中的单词？
对不在字典中的单词进行BKTree搜索，生成候选纠正词。
系统如何选择最佳的拼写纠正？
使用评分算法从候选纠正词中选择最佳纠正，优先考虑前缀匹配和词频。
未来对拼写纠正系统有什么计划？
未来计划利用相同系统实现查询拆分和连接，以提高相关性。
➡️
