[数据结构与算法] 第12周 索引技术 作业题
1:倒排索引
- 描述
给定一些文档，要求求出某些单词的倒排表。
对于一个单词，它的倒排表的内容为出现这个单词的文档编号。
- 输入
- 第一行包含一个数N，1 <= N <= 1000，表示文档数。
接下来N行，每行第一个数ci，表示第i个文档的单词数。接下来跟着ci个用空格隔开的单词，表示第i个文档包含的单词。文档从1开始编号。1 <= ci <= 100。
接下来一行包含一个数M，1 <= M <= 1000，表示查询数。
接下来M行，每行包含一个单词，表示需要输出倒排表的单词。
每个单词全部由小写字母组成，长度不会超过256个字符，大多数不会超过10个字符。 - 输出
- 对于每一个进行查询的单词，输出它的倒排表，文档编号按从小到大排序。
如果倒排表为空，输出"NOT FOUND"。 - 样例输入
3 2 hello world 4 the world is great 2 great news 4 hello world great pku
- 样例输出
1 1 2 2 3 NOT FOUND
離線處理，將每個請求單詞都先讀進來，再掃描一次字典，將答案映射回去。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
char s[1024], query[1024][260];
vector<string> doc[1024];
map<string, set<int> > Q;
set<int> R[1024];
int main() {
int n, m;
int i, j, k;
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &m);
for(j = 0; j < m; j++) {
scanf("%s", s);
doc[i].push_back(s);
}
}
scanf("%d", &m);
for(i = 0; i < m; i++) {
scanf("%s", query[i]);
Q[query[i]].insert(i);
}
for(i = 0; i < n; i++) {
for(j = 0; j < doc[i].size(); j++) {
map<string, set<int> >::iterator it = Q.find(doc[i][j]);
if(it != Q.end()) {
for(set<int>::iterator jt = it->second.begin();
jt != it->second.end(); jt++) {
R[*jt].insert(i);
}
}
}
}
for(i = 0; i < m; i++) {
int flag = 0;
for(set<int>::iterator it = R[i].begin();
it != R[i].end(); it++) {
if(flag) putchar(' ');
flag = 1;
printf("%d", *it + 1);
}
if(R[i].size() == 0)
printf("NOT FOUND");
puts("");
}
return 0;
}
2:倒排索引查询
- 描述
现在已经对一些文档求出了倒排索引，对于一些词得出了这些词在哪些文档中出现。
要求对于倒排索引实现一些简单的查询，即查询某些词同时出现，或者有些词出现有些词不出现的文档有哪些。
- 输入
- 第一行包含一个数N，1 <= N <= 1000，表示倒排索引表的数目。
接下来N行，每行第一个数ci，表示这个词出现在了多少个文档中。接下来跟着ci个数，表示出现在的文档编号，编号不一定有序。1 <= ci <= 1000，文档编号为32位整数。
接下来一行包含一个数M，1 <= M <= 100，表示查询的数目。
接下来M行每行N个数，每个数表示这个词要不要出现，1表示出现，-1表示不出现，0表示无所谓。数据保证每行至少出现一个1。 - 输出
- 共M行，每行对应一个查询。输出查询到的文档编号，按照编号升序输出。
如果查不到任何文档，输出"NOT FOUND"。 - 样例输入
3 3 1 2 3 1 2 1 3 3 1 1 1 1 -1 0 1 -1 -1
- 样例输出
NOT FOUND 1 3 1
先對找到包含有 1 個集合，開始對其集合著手替除的操作。
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
int i, j, k, x;
vector<int> keyword[1024];
set<int> keywordII[1024];
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%d", &m);
while(m--) {
scanf("%d", &x);
keyword[i].push_back(x);
keywordII[i].insert(x);
}
}
scanf("%d", &m);
int c[1024];
while(m--) {
for(i = 0; i < n; i++)
scanf("%d", &c[i]);
set<int> ret;
for(i = 0; i < n; i++) {
if(c[i] == 1) {
for(j = 0; j < keyword[i].size(); j++)
ret.insert(keyword[i][j]);
break;
}
}
for(i = 0; i < n; i++) {
if(c[i] == -1) {
for(j = 0; j < keyword[i].size(); j++) {
ret.erase(keyword[i][j]);
}
}
if(c[i] == 1) {
for(set<int>::iterator it = ret.begin();
it != ret.end(); ) {
if(keywordII[i].find(*it) == keywordII[i].end())
ret.erase(it++);
else
++it;
}
}
}
if(ret.size() == 0)
puts("NOT FOUND");
else {
int f = 0;
for(set<int>::iterator it = ret.begin();
it != ret.end(); it++) {
if(f) putchar(' ');
f = 1;
printf("%d", *it);
}
puts("");
}
}
return 0;
}