ES

Basic

什么是倒排索引

倒排索引是一种用于快速查找文档中单词出现位置的数据结构。

它是搜索引擎中最核心的数据结构之一，与传统的"文档→单词"正向索引相反，倒排索引是"单词→文档"的映射关系。

正向索引 vs 倒排索引

正向索引：文档ID → 文档内容（单词列表）
倒排索引：单词 → 文档ID列表（包含该单词的所有文档）

假设我们有3个文档：

文档1："Python is a programming language"
文档2："Python is named after Monty Python"
文档3："Programming is fun"

构建的倒排索引：

{
    "python": [1, 2],
    "is": [1, 2, 3],
    "a": [1],
    "programming": [1, 3],
    "language": [1],
    "named": [2],
    "after": [2],
    "monty": [2],
    "fun": [3]
}

Python实现倒排索引

import re
from collections import defaultdict
 
def build_inverted_index(documents):
    """
    构建倒排索引
    
    参数:
        documents: 文档列表，每个文档是一个字符串
        
    返回:
        倒排索引字典 {词: [包含该词的文档ID列表]}
    """
    inverted_index = defaultdict(list)
    
    for doc_id, doc in enumerate(documents, start=1):
        # 使用正则表达式分割单词，并转为小写
        words = re.findall(r'\w+', doc.lower())
        
        for word in set(words):  # 使用set去重，避免同一文档多次记录
            inverted_index[word].append(doc_id)
            
    return inverted_index
 
def search(inverted_index, query):
    """
    使用倒排索引搜索
    
    参数:
        inverted_index: 倒排索引字典
        query: 查询字符串
        
    返回:
        包含查询词的文档ID列表
    """
    words = re.findall(r'\w+', query.lower())
    if not words:
        return []
    
    # 获取第一个词的文档列表
    result = set(inverted_index.get(words[0], []))
    
    # 与其他词的文档列表取交集
    for word in words[1:]:
        result.intersection_update(inverted_index.get(word, []))
    
    return sorted(result)
 
# 示例文档
documents = [
    "Python is a programming language",
    "Python is named after Monty Python",
    "Programming is fun"
]
 
# 构建倒排索引
inverted_index = build_inverted_index(documents)
print("倒排索引:")
for word, doc_ids in sorted(inverted_index.items()):
    print(f"{word}: {doc_ids}")
 
# 搜索示例
queries = ["Python", "programming", "Python programming", "monty python", "fun is"]
print("\n搜索结果:")
for query in queries:
    print(f"'{query}': {search(inverted_index, query)}")

输出：

倒排索引:
a: [1]
after: [2]
fun: [3]
is: [1, 2, 3]
language: [1]
monty: [2]
named: [2]
programming: [1, 3]
python: [1, 2]
 
搜索结果:
'Python': [1, 2]
'programming': [1, 3]
'Python programming': [1]
'monty python': [2]
'fun is': [3]

场景：

词频（Term Frequency）：单词在文档中出现的次数
位置信息：单词在文档中出现的位置（用于短语查询）
权重信息：如TF-IDF值

对比：

索引类型	适用场景	倒排索引优势
B+树（MySQL）	精确匹配（如`WHERE id=123`）	无法高效支持模糊搜索
哈希索引	等值查询（如Redis的K-V）	不支持范围或部分匹配
向量索引	语义搜索（如“类似图片”）	需倒排索引补充关键词过滤

ES夯实基础

ES

Basic

什么是倒排索引