正排索引与倒排索引什么是正排索引(forward index)?
由key查询实体的过程,是正排索引.
在搜索引擎中每个文件都对应一个文件ID,文件内容被表示为一系列关键词的集合(实际上在搜索引擎索引库中,关键词也已经转换为关键词ID。简单的,正排索引可以理解为(文件内容会对应一个分词后的集合list<< item >>) Map< id,list< item>>,能够由id快速(时间复杂度O(1))找到内容的一个数据结构。
什么是倒排索引(inverted index)?
由item查询key的过程,是倒排索引。
倒排索引可以理解为Map< item, list< id>>,能够由查询词快速(时间复杂度O(1))找到包含这个查询词的文件的数据结构。
举例:
分词之后的正排索引Map< id, list< item>>
分词后倒排索引
简单的倒排索引Map< item,list< id>>
有单词频率信息(TF)的倒排索引Map< item,list< (id;TF)>>
在单词对应的倒排列表中不仅记录了文档编号,还记载了单词频率信息,即这个单词在某个文档中的出现次数,之所以要记录这个信息,是因为词频信息在搜索结果排序时,计算查询和文档相似度是很重要的一个计算因子,将其记录在倒排列表中,以方便后续排序时进行分值计算。
有单词频率和出现位置(pos)信息的倒排索引Map< item,list<(id;TF;< pos>)>>
检索过程?
简单来讲:先分词,再找到每个item对应的list< id>,最后进行集合求交集的过程。分词和倒排查询时间复杂度都是O(1),整个搜索的时间复杂度取决于“求list< id>的交集”,因此实际上问题也变成了求两个集合的交集。
懂得倾听别人的忠告。