智能提示对于搜索非常重要，相对于机器学习，可以称为集体学习，用集体智慧来识别用户查询，用很小的成本换来较大的收益
我2007年的时候做一个智能提示事先准备好数据的智能提示，那是基于直接想法的设计，这个方案有两个问题
- 需要事先准备数据，更新有点麻烦
- 内存开销极大，一个长度为N的字符串，最后需要 N*(N+1)/2 个Byte的存储,相当于空间 开销为 ∑(N的平方)
当年用于几千条数据集的项目，还能用
当我从事搜索引擎开发之后，按照搜索引擎处理倒排表的原理，重新开发了一个智能提示，代码用nodejs开发,已经开源:https://code.****.net/lutaf/autocomplete，在线上工作良好
- 核心代码只有100行，可以用于千万数据规模
- 做了一个简单的demo，用node运行之后，可以直接看到效果
原理
- 把需要检索的原始语料，一行一条，按字母顺序排列好，相当于一个
std::vector<string> - 检索的时候，用二分法在这个vector中检索，找到第一个满足
startswith(query)==true的 元素 - 从这个元素的index开始，分别 向前查找，向后查找，还是用
startswith(query)==true这个条件，这样就能把语料中所有满足这个query的数据全部找出来 - 然后按照自行定义的rank逻辑，取出一定的数据
倒排表的原理
倒排表从抽象角度，可以定义为 hash_map<string,vector<int> docs > 注意，这只是抽象角度
我做的第一个版本智能提示，就是完全按照这个抽象结构来实现，好处很明显，检索速度最快 O(1),缺点也很明显:如果数据库有几百万条，内存完全不够用，另外运维也繁琐
第二个版本的智能提示,是直接load文件，排序成数组，然后二分法检索，查询时间开销是 lg(N)+M，但是非常节省内存
工业界的搜索引擎做倒排索引表，都是用第二个版本，包括Lucence的索引，也是用这种方法。
在有序数组上做二分法查找，除了性能比较优秀之外，还有如下优点
结构简单，可以把整个有序数组序列化为硬盘文件，然后用mmap打开，这样就能突破服务器内存容量的限制(在96G内存的机器上，可以用mmap打开300G的文件),程序初始化速度极快，故障恢复能力强
hash_map是只能find_by_key,无法做range检索和比较查询，所以只能用来查询字符串. 因此数据库字段建立索引一般不会用hash索引，mysql的索引就是用B+ tree ,这是二叉树的一种变型，而二叉树其实 就是把二分法查询用空间结构固化下来
二叉树付出了空间开销，得到好处是 插入删除 操作很快，适合用于数据库这类可读可写的索引，而搜索引擎都是静态离线版，在排好序的数组上做二分法最优
Trie树 字符树
前缀字符串的查找，hash_map并不是效率最高的做法，时间开销最小的方法是用 Tire-tree，查询时间开销=length(query),并且和数据集的规模完全无关
这个世界上没有银弹，这听起来如此美妙的方法，肯定要付出不菲的门票. Tire树 的空间开销极大，假设只存放asicc码，那么每个节点有 256个子节点，一个N层的完全256叉树，总节点数量=256的N-1次方，不堪重负
为了减少Tire树的空间消耗，大家又提出了多种改良方案
Double-Array Trie，经典双数组结构，把字符树的空间开销完全降下来了，但是算法很难看懂，这个结构的缺点是初始化速度慢的惊人，如果数据规模大，也很难用
Ternary Search Tree，三叉搜索树，顾名思义，每个节点只有3个子节点，它在字符串的检索效率和空间消耗之间做了一个平衡。以前在门户工作的时候，我用这个来做敏感词过滤，简单好用
本文地址: http://lutaf.com/223.htm 鲁塔弗原创文章，欢迎转载，请附带原文链接