【文件属性】：
文件名称：leetcode打不开-autocomplete-system-design:自动完成系统设计
文件大小：2.39MB
文件格式：ZIP
更新时间：2021-06-30 02:06:26
系统开源
leetcode打不开写代码
系统的要求和目标
功能需求
当用户输入他们的查询时，我们的服务应该建议从用户输入的任何内容开始的前
10
个术语。
结果中只应显示一小时窗口内出现频率超过
1000
的搜索词
结果中只应显示过去
7
天内的搜索词
能够根据盗版/法律问题过滤几个关键字
非功能需求
建议应实时显示。
用户应该能够在
200
毫秒内看到建议。
不在范围内
没有拼写检查
无语言环境
没有个人信息
只能说英语
不区分大小写
设计约束
高性能，响应速度应该比用户输入速度快，比方说
<
200ms
对结果准确性和系统可用性没有严格要求
体积限制
每天
50
亿次搜索
算法
数据结构
我们不能为此依赖某个数据库；
我们需要以高效的数据结构将索引存储在内存中。
可以为我们的目的服务的最合适的数据结构之一是
Trie。
trie
是一种树状数据结构，用于存储短语，其中每个节点以顺序方式存储短语的一个字符。
例如，如果我们需要在树中存储“cap、cat、caption、captain、capital”，它看起来像：
我们可以合并只有一个分支的节点以节省存储空间。
上面的
trie
可以这样存储
【文件预览】：
autocomplete-system-design-master
----.DS_Store(6KB)
----assets()
--------trie-example.png(254KB)
--------.DS_Store(6KB)
--------trie-for-physical-storage.png(118KB)
--------compressed-trie.png(134KB)
--------trie-on-single-machine.png(361KB)
--------trie-multi-shard.png(412KB)
--------trie-with-topk.png(322KB)
--------trie-simple-shard.png(396KB)
--------collect-phrase.png(336KB)
--------autocomplete-example.png(153KB)
----README.md(15KB)