返回文章列表

用 Rust 从零实现倒排索引:全文搜索的底座只有三个数据结构

615 字·5 分钟阅读
Rust从零造轮子搜索

"搜索"这个词被用得太随便了。数据库的 LIKE '%关键词%' 也叫搜索,Elasticsearch 也叫搜索,但它们的本质完全不同。

前者是扫描:逐行检查有没有子串。后者是索引:预先建立起"词 → 文档"的映射,查询时直接查表。

这篇从零实现倒排索引。写完你会发现,搜索引擎的骨架比想象中朴素得多。


先看正排和倒排的区别

假设有三篇文档:

doc 1: "rust 异步编程 入门"
doc 2: "rust 所有权 详解"
doc 3: "异步 编程 实践"

正排索引是"文档 → 它包含的词",这也是文档本来的样子。要查"哪些文档包含 rust",只能遍历所有文档。

倒排索引把这个关系反过来:

rust   -> [1, 2]
异步   -> [1, 3]
编程   -> [1, 3]
入门   -> [1]
所有权 -> [2]
详解   -> [2]
实践   -> [3]

于是查"包含 rust 的文档"变成了一次哈希查找,O(1)。

倒排索引的本质就是"反向的正排索引"。 一句话说完了。

三个核心结构

一个完整的倒排索引由三部分组成:

pub struct InvertedIndex {
    /// 1. 词典:词 -> 倒排表在 postings 里的位置
    dictionary: std::collections::HashMap<String, TermInfo>,
 
    /// 2. 倒排表:doc_id 的列表(有序列,用于求交集)
    postings: Vec<Posting>,
 
    /// 3. 位置表:每个词在文档里的位置(用于短语查询)
    ///    这里直接放在 Posting 里
    doc_count: usize,
}
 
#[derive(Debug, Clone)]
pub struct TermInfo {
    /// 有多少文档包含这个词
    pub doc_freq: u32,
    /// 指向 postings 的起始位置
    pub postings_start: u32,
    pub postings_len: u32,
}
 
#[derive(Debug, Clone)]
pub struct Posting {
    pub doc_id: u32,
    /// 这个词在这篇文档里出现的次数(term frequency)
    pub term_freq: u32,
    /// 出现的位置,用于短语查询
    pub positions: Vec<u32>,
}

为什么 postings 是独立的 Vec 而不是 HashMap<String, Vec<Posting>>?

因为放在一起会导致大量分散的小分配,缓存不友好。把倒排表连续存放,查询"rust"时读到的是一段连续内存——这对于动辄几百万个 posting 的场景,性能差异是数量级的。

第一步:分词

分词(tokenization)把文本切成词。英文很简单,中文才是真难点。

先做通用部分:转小写、去掉标点、按空白切。

fn tokenize_en(text: &str) -> Vec<String> {
    text.to_lowercase()
        .split(|c: char| !c.is_alphanumeric())
        .filter(|s| !s.is_empty())
        .map(|s| s.to_string())
        .collect()
}

英文还要做词干还原(stemming),否则 running 和 run 是两个不同的词:

/// 极简的英语后缀剥离(真实实现用 Porter Stemmer)
fn stem_en(word: &str) -> String {
    for suffix in ["ing", "ed", "s", "ly"] {
        if word.len() > suffix.len() + 2 && word.ends_with(suffix) {
            return word[..word.len() - suffix.len()].to_string();
        }
    }
    word.to_string()
}

中文分词的现实

中文没有空格,"异步编程入门" 要怎么切?三种主流方案:

方案 原理 优点 缺点
按字切 每个汉字一个 token 简单,召回高 精度差,索引大
二元切分(bigram) 每两个相邻字 简单,召回高 索引更大
词典 + 统计 词库匹配 + HMM 精度好 需要词典

工程上最省事、效果也不差的是二元切分:

fn tokenize_zh_bigram(text: &str) -> Vec<String> {
    let chars: Vec<char> = text
        .chars()
        .filter(|c| !c.is_whitespace() && !c.is_ascii_punctuation())
        .collect();
 
    let mut tokens = Vec::with_capacity(chars.len());
    for w in chars.windows(2) {
        tokens.push(w.iter().collect());
    }
    tokens
}

"异步编程" 切出来是 ["异步", "步编", "编程"]——windows(2) 是滑动窗口,依次取 异+步、步+编、编+程。

查询时同样切:查"异步"这个词,会变成 ["异步"](只有一个 bigram),然后去索引里找。

bigram 的好处是"不需要词典也能召回":用户搜"编程入门",切出 ["编程", "程入", "入门"],只要文档里有"编程"和"入门"(无论中间隔了什么),就能匹配上。

代价是索引膨胀:每个汉字都参与两个 bigram,索引大小大约是按词切分的 2-3 倍。

中文分词没有免费的午餐:要精度就要词典,要简单就要牺牲索引体积。 生产系统(如 Elasticsearch 的 IK 分词器)选的是"词典 + 统计",因为索引体积换得回来。

第二步:构建倒排表

遍历所有文档,切词,往倒排表里塞:

pub struct IndexBuilder {
    /// 临时结构:词 -> (doc_id -> positions)
    temp: std::collections::HashMap<String, std::collections::HashMap<u32, Vec<u32>>>,
    doc_count: usize,
    /// 每篇文档的长度(词数),BM25 需要
    doc_lengths: Vec<u32>,
}
 
impl IndexBuilder {
    pub fn add_document(&mut self, doc_id: u32, text: &str) {
        let tokens = tokenize(text);
 
        for (pos, token) in tokens.iter().enumerate() {
            self.temp
                .entry(token.clone())
                .or_default()
                .entry(doc_id)
                .or_default()
                .push(pos as u32);
        }
 
        self.doc_lengths.push(tokens.len() as u32);
        self.doc_count += 1;
    }
}

为什么要用两层的 HashMap? 因为构建阶段最重要的是"能按 doc_id 聚合位置"。最后再展开成扁平的 postings 列表。

构建完成后展开:

    pub fn build(self) -> InvertedIndex {
        let mut dictionary = std::collections::HashMap::new();
        let mut postings = Vec::new();
 
        for (term, docs) in self.temp {
            let start = postings.len() as u32;
 
            // doc_id 必须排序!这是后面求交集的前提
            let mut doc_ids: Vec<u32> = docs.keys().copied().collect();
            doc_ids.sort_unstable();
 
            for doc_id in &doc_ids {
                let mut positions = docs[doc_id].clone();
                positions.sort_unstable();
 
                postings.push(Posting {
                    doc_id: *doc_id,
                    term_freq: positions.len() as u32,
                    positions,
                });
            }
 
            dictionary.insert(
                term,
                TermInfo {
                    doc_freq: doc_ids.len() as u32,
                    postings_start: start,
                    postings_len: (postings.len() as u32) - start,
                },
            );
        }
 
        InvertedIndex {
            dictionary,
            postings,
            doc_count: self.doc_count,
            doc_lengths: self.doc_lengths,
        }
    }

"doc_id 必须排序"是一条硬要求,不是优化。后面所有集合运算都建立在"有序"这个前提上。

倒排表按 doc_id 有序,是搜索引擎能用 O(n+m) 做多词交集的基础。 没排序就只能用哈希集合,那会丢掉位置信息的顺序性。

第三步:查询——多词求交集

查 "rust 异步" 要返回"同时包含两个词的文档"。这就是有序列表求交集:

/// 两个有序列表求交集,O(n + m)
fn intersect(a: &[u32], b: &[u32]) -> Vec<u32> {
    let mut result = Vec::new();
    let (mut i, mut j) = (0, 0);
 
    while i < a.len() && j < b.len() {
        match a[i].cmp(&b[j]) {
            std::cmp::Ordering::Equal => {
                result.push(a[i]);
                i += 1;
                j += 1;
            }
            std::cmp::Ordering::Less => i += 1,
            std::cmp::Ordering::Greater => j += 1,
        }
    }
    result
}

这一步就是"跳表/有序列表求交"的经典实现,复杂度 O(n+m) 而非 O(n×m)。

工程上有个重要优化:先按 doc_freq 从小到大排序,再依次求交。

    pub fn search_and(&self, terms: &[String]) -> Vec<u32> {
        // 把词按出现文档数升序排列
        let mut lists: Vec<Vec<u32>> = terms
            .iter()
            .filter_map(|t| self.postings_for(t))
            .collect();
 
        if lists.is_empty() {
            return Vec::new();
        }
        lists.sort_by_key(|l| l.len());
 
        // 从最短的开始交,让中间结果尽快变小
        let mut result = lists[0].clone();
        for list in &lists[1..] {
            if result.is_empty() {
                break; // 空集,不用再算
            }
            result = intersect(&result, list);
        }
        result
    }

为什么先交最短的? 因为中间结果会越来越小。假设三个词分别出现在 100 万、1000、10 篇文档里——先交 10 和 1000,得到最多 10 个候选,再和 100 万求交时,几乎不用遍历。

反过来先交 100 万和 1000,中间结果可能还是很大,白白浪费。

第四步:短语查询

"异步编程" 作为短语(而不是两个独立的词)要相邻才算匹配。这就是位置表的用途:

    pub fn search_phrase(&self, terms: &[String]) -> Vec<u32> {
        if terms.len() == 1 {
            return self.search_and(terms);
        }
 
        // 先求交集拿到候选文档
        let candidates = self.search_and(terms);
        let mut result = Vec::new();
 
        for doc_id in candidates {
            // 逐个检查:第 i 个词的位置 +1 是否等于第 i+1 个词的位置
            if self.positions_match(doc_id, terms) {
                result.push(doc_id);
            }
        }
        result
    }
 
    fn positions_match(&self, doc_id: u32, terms: &[String]) -> bool {
        let positions: Vec<&Vec<u32>> = terms
            .iter()
            .filter_map(|t| self.get_positions(t, doc_id))
            .collect();
 
        if positions.len() != terms.len() {
            return false;
        }
 
        // 以第一个词的位置为锚点,检查后续词是否依次相邻
        for &start in positions[0] {
            let matched = positions[1..].iter().enumerate().all(|(i, pos)| {
                let expected = start + i as u32 + 1;
                pos.binary_search(&expected).is_ok()
            });
            if matched {
                return true;
            }
        }
        false
    }

位置表是"短语查询"和"邻近度评分"的唯一依赖。 没有它,倒排索引只能做"词袋"检索。代价是索引体积大约翻倍——因为每个词都要存它的所有位置。

第五步:排序——BM25

拿到候选文档后,要按相关性排序。最经典的是 TF-IDF,而 BM25 是它的改进版,几乎是所有现代搜索引擎的默认选择。

先理解直觉:

  • TF(词频):一个词在文档里出现越多,文档越相关。但边际递减——出现 100 次不比出现 10 次相关 10 倍。
  • IDF(逆文档频率):一个词在越少的文档里出现,它越有区分度。"的"出现在所有文档里,等于没用;"所有权"只在少数文档里出现,很有价值。
  • 文档长度归一化:长文档天然更容易命中词,要打个折扣。

BM25 的公式:

score(D, Q) = Σ IDF(qi) * (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * |D| / avgdl))
 
其中:
  IDF(qi) = ln(1 + (N - df + 0.5) / (df + 0.5))
  tf      = 词在文档中的出现次数
  |D|     = 文档长度
  avgdl   = 平均文档长度
  k1      = 1.2 ~ 2.0(TF 饱和速度)
  b       = 0.75(长度归一化程度)

代码:

const K1: f32 = 1.2;
const B: f32 = 0.75;
 
impl InvertedIndex {
    pub fn bm25(&self, term: &str, posting: &Posting, avgdl: f32) -> f32 {
        let Some(info) = self.dictionary.get(term) else {
            return 0.0;
        };
 
        // IDF
        let n = self.doc_count as f32;
        let df = info.doc_freq as f32;
        let idf = (1.0 + (n - df + 0.5) / (df + 0.5)).ln();
 
        // TF 饱和
        let tf = posting.term_freq as f32;
        let dl = self.doc_lengths[posting.doc_id as usize] as f32;
        let norm = 1.0 - B + B * (dl / avgdl);
 
        idf * (tf * (K1 + 1.0)) / (tf + K1 * norm)
    }
}

两个参数的作用值得单独说:

  • k1 控制"词频饱和速度"。k1 越大,词频的影响越持久;越小,出现几次就饱和了。
  • b 控制"长度归一化的强度"。b = 0 完全不做归一化(长文档占便宜),b = 1 完全归一化。

b 是非常容易被忽略、但对排序质量影响巨大的参数。 短文档集合(比如商品标题)可以设 b = 0.3 左右,长文档(论文全文)用默认 0.75。

完整查询流程

    pub fn search(&self, query: &str, top_k: usize) -> Vec<(u32, f32)> {
        let terms = tokenize(query);
        if terms.is_empty() {
            return Vec::new();
        }
 
        let avgdl = self.doc_lengths.iter().sum::<u32>() as f32 / self.doc_count as f32;
 
        // 1. 求候选集(多词交集)
        let candidates = self.search_and(&terms);
 
        // 2. 对每个候选打分
        let mut scored: Vec<(u32, f32)> = candidates
            .into_iter()
            .map(|doc_id| {
                let mut score = 0.0;
                for term in &terms {
                    if let Some(posting) = self.get_posting(term, doc_id) {
                        score += self.bm25(term, posting, avgdl);
                    }
                }
                (doc_id, score)
            })
            .collect();
 
        // 3. 按分数排序,取 top k
        scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap());
        scored.truncate(top_k);
        scored
    }

注意这里用的是"交集"(AND 语义)。 真实搜索引擎用的是 OR + 打分:任何词命中都可能相关,只是分数不同。AND 更适合"精确查找"场景。

想改成 OR,只需把 intersect 换成 union,其他不变。打分环节本来就是按每个词独立算再加总的,天然支持 OR。

压缩:倒排表可以小很多

倒排表的空间瓶颈在 doc_id 列表。有两种经典的压缩:

1. 差值编码(delta encoding)。 存相邻 doc_id 的差,而不是绝对值:

// [1, 5, 100, 102] -> [1, 4, 95, 2]
fn delta_encode(ids: &[u32]) -> Vec<u32> {
    let mut out = Vec::with_capacity(ids.len());
    let mut prev = 0;
    for &id in ids {
        out.push(id - prev);
        prev = id;
    }
    out
}

2. 变长整数(varint)。 小数字只占 1 字节:

fn write_varint(mut n: u32, out: &mut Vec<u8>) {
    while n >= 0x80 {
        out.push((n as u8) | 0x80); // 最高位 1 表示"还有后续"
        n >>= 7;
    }
    out.push(n as u8);
}

两者结合,一个 doc_id 平均可以从 4 字节压到 1 字节以内。实际系统(Lucene)还会用位图、跳跃表进一步优化。

搜索引擎的空间优化集中在倒排表上,因为它是整个索引里最大的部分。 词典本身虽然有几十万词条,但每个词只有几十字节。

缓存与合并:工业系统的两个额外话题

到这里功能完整了。但生产级搜索引擎还差两块:

1. 跳跃表(skip list)加速交集。 两个列表求交时,如果每次都逐格前进,遇到稀疏匹配会很慢。在倒排表里每隔若干项插一个"跳跃点",可以快速跳过不可能匹配的区间。

2. 索引分段与合并(segment merge)。 增量索引不能每次都重建——主流做法是"新文档写进内存小段,满了就刷成不可变段,后台定期合并多个段"。

这和 LSM-Tree 的 compaction 是同一个思路:不可变段 + 后台合并。区别只是合并的是倒排表而不是 SSTable。

结论

倒排索引的骨架只有三样东西:

词典(词 → 倒排表位置);倒排表(有序 doc_id + 词频);位置表(用于短语和邻近度)。

围绕它们展开的所有工作都是工程优化:分词策略(中文的 bigram vs 词典)、高效求交(有序列表 + 短列表优先 + 跳跃表)、相关性排序(BM25 的 k1 和 b)、空间压缩(差值 + 变长整数)、增量更新(分段 + 合并)。

理解了这三个结构,再看 Elasticsearch 的那些配置项,你会知道每一个都在调什么。 下一篇我们去看另一个"前缀检索"的场景——自动补全,那里需要的是另一种结构:Trie。