M06640: 倒排索引

string, implementation, data structure, http://cs101.openjudge.cn/practice/06640/

给定一些文档，要求求出某些单词的倒排表。

对于一个单词，它的倒排表的内容为出现这个单词的文档编号。

输入

第一行包含一个数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

思路：用字典将word作为key，在value中进行文件索引的存储。利用0表示不存在。利用setdefault方法设置默认值。

python

n = int(input())  
dic = {}  
for i in range(n):  
    s = input()[1:].split()  
    for j in set(s):  
        dic.setdefault(j,[]).append(i+1)  
  
m = int(input())  
for i in range(m):  
    word = input()  
    out = sorted(dic.setdefault(word,[0]))  
    out = list(map(str,out))  
    print(' '.join(out) if out[0]!='0' else 'NOT FOUND')

要实现一个程序来创建和查询倒排索引，可以使用字典结构来高效地完成任务。以下是具体的步骤：

首先，解析输入，为每个单词构建倒排索引，即记录每个单词出现在哪些文档中。
使用字典存储倒排索引，其中键为单词，值为一个有序列表，列表中包含出现该单词的文档编号。
对于每个查询，检查字典中是否存在该单词，如果存在，则返回升序文档编号列表；如果不存在，则返回 "NOT FOUND"。

python

from collections import defaultdict
def main():
    n = int(input())
    index = 1
    inverted_index = defaultdict(set)   # 构建倒排索引
    for i in range(1, n + 1):
        parts = input().split()
        doc_id = i
        num_words = int(parts[0])
        words = parts[1:num_words + 1]
        for word in words:
            inverted_index[word].add(doc_id)

    m = int(input())
    results = []

    # 查询倒排索引
    for _ in range(m):
        query = input()
        if query in inverted_index:
            results.append(" ".join(map(str, sorted(list(inverted_index[query])))))
        else:
            results.append("NOT FOUND")

    # 输出查询结果
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

其实每行第一个数字根本没用，读成一个str列表之后取[1:]就行了其他数据结构也完全不需要

python

N = int(input())
lst = []
for _ in range(N):
    lst.append(list(input().split())[1:])
M = int(input())
for _ in range(M):
    s = input().strip()
    ans = []
    for i,m in enumerate(lst):
        if s in m:
            ans.append(i+1)
    print(' '.join(map(str,ans)))

M06640: 倒排索引 ​

M06640: 倒排索引