如何实现搜索引擎的搜索关键词提示功能

捕获.PNG

1. Trie树

一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起

4ca9d9f78f2206cad93836a2b1d6d80d.jpg

2. 应用

实际上，Trie 树的这个应用可以扩展到更加广泛的一个应用上，就是自动输入补全，比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等

3. 多模式串匹配算法：AC 自动机


实现一个高性能的敏感词过滤系统

4. 搜索引擎拼写纠错

如何量化两个字符串之间的相似程度

编辑距离

将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。