问题背景与目标

本题要求实现一个小型搜索引擎，使用倒排索引技术处理文档集合，并根据用户查询返回相关文档的行内容。倒排索引是一种将单词映射到其在文档中出现位置的数据结构，广泛应用于搜索引擎中。

输入输出格式

• 输入：
  • 第一行是一个整数 ( N )，表示文档数量。
  • 接下来是 ( N ) 份文档，每份文档以一行十个星号 ********** 结尾。
  • 然后是一个整数 ( M )，表示查询数量。
  • 接下来是 ( M ) 行查询，查询格式可以是单个术语、AND、OR 或 NOT。
• 输出：
  • 对于每个查询，输出满足条件的文档行。
  • 如果没有找到匹配的文档行，输出 Sorry, I found nothing.。
  • 每个查询的输出以一行十个等号 ========== 结尾。

解题思路

1. 构建倒排索引：

   • 遍历所有文档，对每行进行分词处理，将单词转换为小写，并忽略非字母字符。
   • 使用 map<string, Src> 存储每个单词及其出现的文档和行号（Src 是一个 set<Figure>，Figure 包含文档序号和行号）。
   • 同时使用 map<string, docSrc> 存储每个单词出现的文档序号集合（docSrc 是一个 set<int>）。

2. 处理查询：

   • 单个术语查询：直接从倒排索引中查找单词对应的文档和行号。
   • AND 查询：找到两个单词分别出现的文档序号集合，取交集，然后从交集的文档中找到包含这两个单词的行号。
   • OR 查询：找到两个单词分别出现的文档序号集合，取并集，然后从并集的文档中找到包含这两个单词的行号。
   • NOT 查询：找到单词出现的文档序号集合，从所有文档中排除这些文档，输出剩余文档的所有行。

3. 输出结果：

   • 按照文档序号和行号的顺序输出满足条件的行。
   • 如果没有找到任何行，输出 Sorry, I found nothing.。

代码实现

以下是完整的代码实现：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

class Figure { // 表示单词在文档中的位置
public:
    int docOrder, lineOrder;
    Figure() {}
    Figure(int d, int l) {
        docOrder = d;
        lineOrder = l;
    }
};

bool operator < (const Figure f1, const Figure f2) { // 用于 set 的比较函数
    if (f1.docOrder != f2.docOrder) {
        return f1.docOrder < f2.docOrder;
    } else {
        return f1.lineOrder < f2.lineOrder;
    }
}

class Doc { // 表示文档
public:
    int docOrder, lineLimit;
    Doc() {}
    Doc(int d, int l) {
        this->docOrder = d;
        this->lineLimit = l;
    }
};

typedef set<Figure> Src; // 用于存储单词出现的位置
typedef set<int> docSrc; // 用于存储单词出现的文档序号
map<string, docSrc> docMap; // 单词到文档序号集合的映射
map<string, Src> dict; // 单词到位置集合的映射
map<Figure, string> wordLine; // 位置到行内容的映射
vector<Doc> docs; // 存储所有文档的信息

const string DOC_END = "**********";
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.begin())

void Standard(string &line); // 标准化字符串
void WordRecord(string &line, int docOrder, int lineOrder); // 记录单词到倒排索引
void PrintSrc(Src &src); // 打印结果
void WordsToFigure(Src &src, docSrc &dsrc, string &w1, string &w2); // 处理 AND/OR 查询
void NotWord(string &word, Src &src); // 处理 NOT 查询

int main() {
    int allDocs, queries;

    // 输入文档
    scanf("%d", &allDocs);
    cin.get();
    for (int i = 0; i < allDocs; i++) {
        string line;
        int lineCounter = 0;
        while (getline(cin, line) && line != DOC_END) { // 读取文档内容
            wordLine[Figure(i, lineCounter)] = line;
            Standard(line);
            WordRecord(line, i, lineCounter++);
        }
        docs.push_back(Doc(i, lineCounter));
    }

    // 输入查询
    string command;
    scanf("%d", &queries);
    cin.get();
    while (queries--) {
        getline(cin, command);
        Standard(command);
        Src src;
        if (command.find_last_of(' ') == string::npos) { // 单个单词查询
            src = dict[command];
        } else if (command.find_last_of(' ') != command.find_first_of(' ')) { // AND/OR 查询
            stringstream ss(command);
            string w1, w2, connected;
            ss >> w1 >> connected >> w2;
            docSrc dSrc1 = docMap[w1];
            docSrc dSrc2 = docMap[w2];

            docSrc dsrc;
            if (connected == "and") {
                set_intersection(ALL(dSrc1), ALL(dSrc2), INS(dsrc)); // 交集
            } else {
                set_union(ALL(dSrc1), ALL(dSrc2), INS(dsrc)); // 并集
            }

            WordsToFigure(src, dsrc, w1, w2);
        } else { // NOT 查询
            stringstream ss(command);
            string w1;
            ss >> w1 >> w1;
            NotWord(w1, src);
        }
        PrintSrc(src);
    }
    return 0;
}

void Standard(string &line) {
    int length = line.length();
    for (int i = 0; i < length; i++) {
        if (isalpha(line[i])) {
            line[i] = tolower(line[i]); // 转换为小写
        } else {
            line[i] = ' '; // 非字母字符替换为空格
        }
    }
}

void WordRecord(string &line, int docOrder, int lineOrder) {
    stringstream ss(line);
    string word;
    while (ss >> word) {
        if (dict.count(word)) { // 如果单词已经在字典中
            if (!dict[word].count(Figure(docOrder, lineOrder))) { // 如果该行尚未记录
                dict[word].insert(Figure(docOrder, lineOrder));
            }
        } else {
            Src src;
            src.insert(Figure(docOrder, lineOrder));
            dict[word] = src;
        }
        if (docMap.count(word)) { // 如果单词已经在文档映射中
            docMap[word].insert(docOrder);
        } else {
            docSrc ds;
            docMap[word] = ds;
            docMap[word].insert(docOrder);
        }
    }
}

void PrintSrc(Src &src) {
    if (src.size() == 0) {
        printf("Sorry, I found nothing.\n");
        printf("==========\n");
        return;
    }
    Src::iterator it = src.begin(), bef;
    printf("%s\n", wordLine[*it].c_str());
    bef = it++;
    while (it != src.end()) {
        if (it->docOrder != bef->docOrder) {
            printf("----------\n");
        }
        printf("%s\n", wordLine[*it].c_str());
        bef = it;
        it++;
    }
    printf("==========\n");
}

void WordsToFigure(Src &src, docSrc &dsrc, string &w1, string &w2) {
    docSrc::iterator it;
    for (it = dsrc.begin(); it != dsrc.end(); it++) {
        Src::iterator it2;
        for (it2 = dict[w1].begin(); it2 != dict[w1].end(); it2++) {
            if (*it == it2->docOrder) {
                src.insert(*it2); // 添加 w1 出现的位置
            }
        }
        for (it2 = dict[w2].begin(); it2 != dict[w2].end(); it2++) {
            if (*it == it2->docOrder) {
                src.insert(*it2); // 添加 w2 出现的位置
            }
        }
    }
}

void NotWord(string &word, Src &src) {
    docSrc dsrc = docMap[word];
    vector<Doc>::iterator it;
    for (it = docs.begin(); it != docs.end(); it++) {
        if (!dsrc.count(it->docOrder)) { // 如果文档中不包含该单词
            for (int i = 0; i < it->lineLimit; i++) {
                src.insert(Figure(it->docOrder, i)); // 添加该文档的所有行
            }
        }
    }
}

代码说明

1. Figure 类：

   • 表示一个单词在某个文档的某一行出现。
   • 重载了 < 运算符，用于在 set 中排序。

2. Doc 类：

   • 表示一个文档及其行数。

3. 辅助函数：

   • Standard：将字符串中的字母转换为小写，非字母字符转换为空格。
   • WordRecord：将单词记录到倒排索引中。
   • PrintSrc：按照要求格式输出结果。
   • WordsToFigure：处理 AND 和 OR 查询，找到满足条件的行。
   • NotWord：处理 NOT 查询，找到不包含某个单词的文档的所有行。

4. 主函数：

   • 读取文档并构建倒排索引。
   • 读取查询并根据查询类型调用相应的处理函数。
   • 输出结果。

示例分析

以输入数据为例：

4  
A manufacturer, importer, or seller of  
digital media devices may not (1) sell,  
or offer for sale, in interstate commerce,  
or (2) cause to be transported in, or in a  
manner affecting, interstate commerce,  
a digital media device unless the device  
includes and utilizes standard security  
technologies that adhere to the security  
system standards.  
**********  
Of course, Lisa did not necessarily  
intend to read his books. She might  
want the computer only to write her  
midterm. But Dan knew she came from  
a middle-class family and could hardly  
afford the tuition, let alone her reading  
fees. Books might be the only way she  
could graduate  
**********  
Research in analysis (i.e., the evaluation  
of the strengths and weaknesses of  
computer system) is essential to the  
development of effective security, both  
for works protected by copyright law  
and for information in general. Such  
research can progress only through the  
open publication and exchange of  
complete scientific results  
**********  
I am very very very happy!  
What about you?  
**********  
6  
computer  
books AND computer  
books OR protected  
NOT security  
very  
slick

• 查询 computer：

  • 在第二份文档中找到包含 computer 的行：

    want the computer only to write her
    

• 查询 books AND computer：

  • 找到 books 和 computer 都出现的文档（第二份文档）：

    intend to read his books. She might
    want the computer only to write her
    fees. Books might be the only way she
    

• 查询 books OR protected：

  • 找到包含 books 或 protected 的文档：

    intend to read his books. She might
    fees. Books might be the only way she
    for works protected by copyright law
    

• 查询 NOT security：

  • 找到不包含 security 的文档的所有行：

    Of course, Lisa did not necessarily
    intend to read his books. She might
    want the computer only to write her
    midterm. But Dan knew she came from
    a middle-class family and could hardly
    afford the tuition, let alone her reading
    fees. Books might be the only way she
    could graduate
    I am very very very happy!
    What about you?
    

• 查询 very：

  • 找到包含 very 的行：

    I am very very very happy!
    

• 查询 slick：

  • 没有找到包含 slick 的行，输出：

    Sorry, I found nothing.
    

总结

本题通过构建倒排索引，实现了高效的文档查询功能。倒排索引能够快速定位单词在文档中的位置，结合布尔运算符（AND、OR、NOT）可以灵活处理复杂的查询需求。代码中使用了 set 和 map 等数据结构，确保了查询的高效性和结果的正确性。