倒排索引¶

正排索引以文档为关键字，以词为值，可以方便地插入、删除、修改文档，但是查询单词的效率低；倒排索引以词为关键字，以文档为值，可以方便地查询单词，但是建立和更新索引的效率低。

为了更好地理解倒排索引，可以先看看单词-文档关联矩阵。这个矩阵的行是单词，列是文档，元素是单词是否在文档中出现，显然是一个稀疏矩阵。而倒排索引是链表，每一行会去掉没有出现对应单词的文档，能极大压缩上述稀疏矩阵。

索引的建立¶

倒排表的建立过程是：对于每个文档，对文档中的每个单词，如果单词不在倒排表中，则创建一个新的链表，然后将文档加入到链表中；如果单词在倒排表中，则找到对应的链表，然后将文档加入到链表中。

需要注意的是，文档 ID 可能非常大，因此倒排表 (Posting List) 中实际存储的值可以是前后文档 ID 的差值，这样可以实现压缩 (Compression)。

由此，可将 Index Generator 分为五个部分：

在读入单词时，需要先进行 word stemming，将单词转化为词根，还需要过滤掉 stop words，即那些没有什么实际意义的词

当内存不足时，可以先将倒排表写入磁盘，在最后再合并倒排表，因为一般每个字典都是有序的，所以合并的时候可以用归并排序。

当磁盘也不足时，可以使用分布式倒排索引，这时候有两种存法：

Term-partitioned index: 将倒排表按照单词进行分区，存储一定范围内每个单词的所有文档，更有利于查询
Document-partitioned index: 将倒排表按照文档进行分区，存储一定范围内的文档的倒排表，更有利于安全，即使一部分数据丢失，也不会影响查询

当插入新的文档时，会先存进较小的辅表 (auxiliary index) 中，这样可以减少对主表的修改，然后再定期合并辅表和主表，实现动态索引 (Dynamic Isndexing)。

当删除文档时，可以先将文档标记为删除，然后定期删除标记的文档，这样也可以减少对倒排表的修改。

在查询索引时，可以使用搜索树或者哈希表，其中前者准确率高、能存储顺序，后者速度快、占用内存小。

返回的文档可能非常多，因此需要对文档的权重进行排序，一种可能的方法是根据权威的网站的超链接来判断权重。而且查询的单词也会根据其出现频率进行排序，可以只截取前面频率较低的单词进行查询。

搜索引擎的评价涉及建立索引的效率、查询索引的速度和查询结果的好坏，具体就用户而言，有以下两个方面：

为了评价查询结果的相关性，可以建立一个包括 document, query 以及每个 query-doc 对是否相关的 benchmark，这样对每个查询，就有：

	Relevant	Irrelevant
Retrieved	TP	FP
Not Retrieved	FN	TN

其中 TP 为被判定为正例的正例，FP 为被判定为正例的负例，FN 为被判定为负例的正例，TN 为被判定为负例的负例。这样就可以计算出：