倒排索引详解

文章目录倒排索引Inverted Index正排索引与倒排索引实现优缺点倒排索引Inverted Index倒排索引是信息检索领域最核心的数据结构几乎所有搜索引擎Google、Elasticsearch、Lucene都基于它构建。倒排索引是一种将文档中的词项Term映射到包含该词项的文档列表Document List 的数据结构。通常包含两部分词典Dictionary所有出现过的词项按字典序排序方便二分查找。倒排列表Posting List每个词项对应的文档ID列表有时还记录词频、位置等信息。正排索引与倒排索引当查询“search engine”时正排索引需要遍历所有文档 对每个文档逐一检查是否同时包含两个词而对于倒排索引来说首先要查词典得到两个词的倒排列表search → [Doc1, Doc2] 和 engine → [Doc1, Doc2] 然后再求交集得到 [Doc1, Doc2]实现下面例子中构建好的词典和倒排列表如下所示词典倒排列表and[Doc3(freq1)]are[Doc3(freq1)]both[Doc3(freq1)]great[Doc2(freq2), Doc3(freq3)]i[Doc0(freq1), Doc1(freq1)]is[Doc2(freq1)]java[Doc1(freq3), Doc2(freq1), Doc3(freq1)]love[Doc0(freq2), Doc1(freq1)]programming[Doc0(freq1)]python[Doc3(freq1)]输出结果如下importmathfromcollectionsimportdefaultdictclassInvertedIndex:def__init__(self):self.docs{}# 文档ID - 原始文本self.inverteddefaultdict(dict)# 词 - {doc_id: term_frequency}self.doc_count0# 文档总数defadd_document(self,text):添加一篇文档自动分配IDdoc_idself.doc_count self.docs[doc_id]text# 简单分词转小写按非字母数字分割wordsself._tokenize(text)# 统计词频tf{}forwordinwords:tf[word]tf.get(word,0)1# 更新倒排列表forword,freqintf.items():self.inverted[word][doc_id]freq self.doc_count1def_tokenize(self,text):基础分词小写 按非字母数字分割importre wordsre.findall(r\w,text.lower())returnwordsdefsearch_and(self,query):AND查询返回同时包含所有查询词的文档ID列表termsself._tokenize(query)ifnotterms:return[]# 获取第一个词的文档集合result_setset(self.inverted.get(terms[0],{}).keys())forterminterms[1:]:result_setset(self.inverted.get(term,{}).keys())returnsorted(result_set)defsearch_or(self,query):OR查询返回包含至少一个查询词的文档ID列表termsself._tokenize(query)result_setset()forterminterms:result_set|set(self.inverted.get(term,{}).keys())returnsorted(result_set)deftfidf_score(self,doc_id,term):计算文档doc_id中词term的TF-IDF权重tfself.inverted.get(term,{}).get(doc_id,0)iftf0:return0# 包含该词的文档数dflen(self.inverted.get(term,{}))idfmath.log((self.doc_count1)/(df1))1# 平滑returntf*idfdefsearch_ranked(self,query):根据TF-IDF对AND查询结果排序termsself._tokenize(query)candidate_docsself.search_and(query)# 先求交集scores[]fordoc_idincandidate_docs:scoresum(self.tfidf_score(doc_id,term)forterminterms)scores.append((doc_id,score,self.docs[doc_id]))# 按得分降序排序scores.sort(keylambdax:x[1],reverseTrue)returnscores# 示例使用if__name____main__:indexInvertedIndex()docs[I love love programming,# love 出现2次I love Java Java Java,# love 1次, Java 3次Java is great great,# Java 1次, great 2次Python and Java are both great great great# great 3次, Java 1次]fordocindocs:index.add_document(doc)print(AND查询 love java:,index.search_and(love java))print(OR查询 love java:,index.search_or(love java))print(排序查询 java great:)fordoc_id,score,textinindex.search_ranked(java great):print(f Doc{doc_id}: {text} (score{score:.4f}))优缺点查询速度快直接通过词查文档列表时间复杂度 O(1) 词典查找 O(文档数) 列表合并远快于遍历所有文档O(N)支持复杂度与、或、非AND、OR、NOT可以通过倒排列表的交、并、差高效计算可扩展性好可以分片存储Shard支持海量数据灵活的相关性排序可以存储词频TF、文档长度等实现 TF-IDF、BM25 等排序算法构建和维护成本较高存储空间需求大需要预处理所有文档分词、归一化、排序消耗时间和计算资源新增、删除、修改文档需要重建或更新倒排索引尤其是传统静态索引