专栏文章

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

CCherryCake
P12871题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip25qcu
此快照首次捕获于
2025/12/03 04:56
3 个月前
此快照最后确认于
2025/12/03 04:56
3 个月前
查看原文

题意

在信息检索系统中，需要根据 N-Gram 分词算法实现文档与查询词的匹配：
  • 给定参数 [min⁡,max⁡][\min, \max]，对文档和查询词生成所有长度为 min⁡\min 到 max⁡\max 的滑动窗口子串。
  • 若查询词的任意 N-Gram 出现在某文档的 N-Gram 集合中，则该文档匹配成功。
  • 统计匹配成功的文档数量。

分析

N-Gram 是指将字符串按连续字符窗口截取的子串，窗口长度为 NN。本题中 NN 的范围是 [min⁡,max⁡][\min, \max]，即需要生成所有长度从 minmin 到 maxmax 的连续子串。
生成规则分两种情况。
情况一（字符串长度小于 min⁡\min）：
  • 若字符串长度 len<min⁡len< \min，则无法生成长度为 minmin 的子串，此时 N-Gram 仅包含字符串本身。
情况二（字符串长度大于等于 min⁡\min）：
  • 对每个长度 11，从左到右滑动窗口截取子串，步长为 11。
对每个文档生成所有合法 N-Gram，存入 unordered_set\texttt{unordered\_set} 集合（去重且支持快速查询）。
对查询词生成所有合法 N-Gram，形成序列 PP。
遍历每个文档的 N-Gram 集合，判断 PP 中是否存在至少一个 N-Gram 在集合中。若存在，则文档匹配成功。

代码

以下是 c++ 版的。
CPP
#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 忘了。
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()

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...