倒排索引详解

倒排索引（Inverted Index）

倒排索引是信息检索领域最核心的数据结构，几乎所有搜索引擎（Google、Elasticsearch、Lucene）都基于它构建。

倒排索引是一种将文档中的词项（Term）映射到包含该词项的文档列表（Document List） 的数据结构。通常包含两部分：

• 词典（Dictionary）：所有出现过的词项，按字典序排序，方便二分查找。
• 倒排列表（Posting List）：每个词项对应的文档ID列表，有时还记录词频、位置等信息。

正排索引与倒排索引

当查询“search engine”时，正排索引需要遍历所有文档， 对每个文档逐一检查是否同时包含两个词，

而对于倒排索引来说，首先要查词典得到两个词的倒排列表：search → [Doc1, Doc2] 和 engine → [Doc1, Doc2] ，然后再求交集得到 [Doc1, Doc2]

实现

下面例子中构建好的词典和倒排列表如下所示，

输出结果如下：

importmathfromcollectionsimportdefaultdictclassInvertedIndex:def__init__(self):self.docs={}# 文档ID -> 原始文本self.inverted=defaultdict(dict)# 词 -> {doc_id: term_frequency}self.doc_count=0# 文档总数defadd_document(self,text):"""添加一篇文档，自动分配ID"""doc_id=self.doc_count self.docs[doc_id]=text# 简单分词：转小写，按非字母数字分割words=self._tokenize(text)# 统计词频tf={}forwordinwords:tf[word]=tf.get(word,0)+1# 更新倒排列表forword,freqintf.items():self.inverted[word][doc_id]=freq self.doc_count+=1def_tokenize(self,text):"""基础分词：小写 + 按非字母数字分割"""importre words=re.findall(r'\w+',text.lower())returnwordsdefsearch_and(self,query):"""AND查询：返回同时包含所有查询词的文档ID列表"""terms=self._tokenize(query)ifnotterms:return[]# 获取第一个词的文档集合result_set=set(self.inverted.get(terms[0],{}).keys())forterminterms[1:]:result_set&=set(self.inverted.get(term,{}).keys())returnsorted(result_set)defsearch_or(self,query):"""OR查询：返回包含至少一个查询词的文档ID列表"""terms=self._tokenize(query)result_set=set()forterminterms:result_set|=set(self.inverted.get(term,{}).keys())returnsorted(result_set)deftfidf_score(self,doc_id,term):"""计算文档doc_id中词term的TF-IDF权重"""tf=self.inverted.get(term,{}).get(doc_id,0)iftf==0:return0# 包含该词的文档数df=len(self.inverted.get(term,{}))idf=math.log((self.doc_count+1)/(df+1))+1# 平滑returntf*idfdefsearch_ranked(self,query):"""根据TF-IDF对AND查询结果排序"""terms=self._tokenize(query)candidate_docs=self.search_and(query)# 先求交集scores=[]fordoc_idincandidate_docs:score=sum(self.tfidf_score(doc_id,term)forterminterms)scores.append((doc_id,score,self.docs[doc_id]))# 按得分降序排序scores.sort(key=lambdax:x[1],reverse=True)returnscores# 示例使用if__name__=="__main__":index=InvertedIndex()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 等排序算法
• 构建和维护成本较高，存储空间需求大：需要预处理所有文档，分词、归一化、排序，消耗时间和计算资源，新增、删除、修改文档需要重建或更新倒排索引（尤其是传统静态索引）