[蓝桥杯 2025 国 Python A] 倒排索引

CherryCake · 2025-06-21 11:42:57 · 题解

题意

在信息检索系统中，需要根据 N-Gram 分词算法实现文档与查询词的匹配：

• 给定参数 [\min, \max]，对文档和查询词生成所有长度为 \min 到 \max 的滑动窗口子串。
• 若查询词的任意 N-Gram 出现在某文档的 N-Gram 集合中，则该文档匹配成功。
• 统计匹配成功的文档数量。

  分析

  N-Gram 是指将字符串按连续字符窗口截取的子串，窗口长度为 N。本题中 N 的范围是 [\min, \max]，即需要生成所有长度从 min 到 max 的连续子串。

生成规则分两种情况。

情况一（字符串长度小于 \min）：

• 若字符串长度 len< \min，则无法生成长度为 min 的子串，此时 N-Gram 仅包含字符串本身。

情况二（字符串长度大于等于 \min）：

• 对每个长度 1，从左到右滑动窗口截取子串，步长为 1。

对每个文档生成所有合法 N-Gram，存入 \texttt{unordered\_set} 集合（去重且支持快速查询）。

对查询词生成所有合法 N-Gram，形成序列 P。

遍历每个文档的 N-Gram 集合，判断 P 中是否存在至少一个 N-Gram 在集合中。若存在，则文档匹配成功。

代码

以下是 c++ 版的。

#include <bits/stdc++.h>
using namespace std;
int n,minl,maxl;
vector<string> gngrams(const string& s,int minl,int maxl){
    vector<string> ngrams;
    int len=s.size();
    if(len<minl){
        ngrams.push_back(s);
        return ngrams;
    }
    for(int l=minl;l<=maxl&&l<=len;l++){
        for(int i=0;i<=len-l;i++) ngrams.push_back(s.substr(i,l));
    }
    return ngrams;
}
int main(){
    cin>>n>>minl>>maxl;
    vector<unordered_set<string>> dngrams(n);
    for(int i=0;i<n;i++){
        string d;
        cin>>d;
        vector<string>ngrams=gngrams(d,minl,maxl);
        for(const string& ng:ngrams) dngrams[i].insert(ng);
    }
    string q;
    cin>>q;
    vector<string> qngrams=gngrams(q,minl,maxl);
    int cnt=0;
    for(int i=0;i<n;i++){
        for(const string& qng:qngrams){
            if(dngrams[i].count(qng)){
                cnt++;
                break; 
            }
        }
    }
    cout<<cnt;
    return 0;
}

代码 Python 版（AI 辅助生成）

作者其实把 Python 忘了。

def generate_ngrams(s, min_length, max_length):
    """生成字符串的 n-gram 列表"""
    ngrams = []
    length = len(s)

    # 当字符串长度小于最小 n-gram 长度时，直接返回原字符串
    if length < min_length:
        ngrams.append(s)
        return ngrams

    # 生成指定长度范围内的所有 n-gram
    for l in range(min_length, max_length + 1):
        if l > length:
            continue
        for i in range(length - l + 1):
            ngrams.append(s[i:i+l])

    return ngrams

def main():
    # 读取输入
    n, min_length, max_length = map(int, input().split())

    # 存储每个文档的 n-gram 集合
    document_ngrams = [set() for _ in range(n)]

    # 处理每个文档并生成 n-gram
    for i in range(n):
        document = input()
        ngrams = generate_ngrams(document, min_length, max_length)
        document_ngrams[i].update(ngrams)

    # 处理查询字符串
    query = input()
    query_ngrams = generate_ngrams(query, min_length, max_length)

    # 计算匹配的文档数量
    count = 0
    for i in range(n):
        # 只要查询的 n-gram 中有一个存在于文档的 n-gram 集合中，即计数
        for ng in query_ngrams:
            if ng in document_ngrams[i]:
                count += 1
                break  # 找到一个匹配就可以停止检查该文档

    # 输出结果
    print(count)

if __name__ == "__main__":
    main()