搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解

搜索引擎中倒排表数据结构、通配符查询、拼写纠正详解2015-10-16搜索引擎里的dictionary data通常存储着这些信息：

索引词（term vocabulary）。

文档频率（document frequency，即这个词在多少个文档里出现）。

指向倒排表的指针（pointers to each postings list ）。

那么，他是怎样的一个数据结构呢？

一种非常naive的词典结构就是：

其中，term的类型是char[20]，占20bytes，document frequency类型int，占4-8 bytes，pointer指针占4-8 bytes。

这种数组的存储方式会有两个问题：

空间上：How do we store a dictionary in memory efficiently？

时间上：How do we quickly look up elements at query time？

当然，比较好的数据结构是：

1，Hashtables。2，Trees。

（一些搜索引擎用的是Hashtables，一些用的是trees。）

其实，具体判断该选择什么样的数据结构，主要从以下三点来衡量：

1，数据是不是持续增长的？

2，访问查找是不是很频繁？

3，词典的规模是不是很大？

具体来看看Hashtables和Trees。

如果用的是Hashtables，那么每一个索引词都会被一个hash函数转换成一个整数。

优点：

查找起来十分迅速，时间是O（1）。

缺点：

如果两个词相差十分的小，不容易发现。比如说 judgment/judgement 。

无法实现前缀查询。即查询所有给点前缀的词。

如果词典是持续增长的，需要时不时的对原来的hashtables重新进行hash计算，这个代价是很大的。