2013-12-27 20:45:19Morris

[数据结构与算法] 第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;
}