04093: 倒排索引查询
Inverted Index, http://cs101.openjudge.cn/practice/04093/
现在已经对一些文档求出了倒排索引，对于一些词得出了这些词在哪些文档中出现的列表。
要求对于倒排索引实现一些简单的查询，即查询某些词同时出现，或者有些词出现有些词不出现的文档有哪些。
输入
第一行包含一个数N，1 <= N <= 100，表示倒排索引表的数目。 接下来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在实际搜索引擎在处理基于倒排索引的查询时，搜索引擎确实会优先关注各个查询词的倒排表的合并和交集处理，而不是直接准备未出现文档的集合。这种方法更有效，特别是在处理大规模数据集时，因为它允许系统动态地调整和优化查询过程，特别是在有复杂查询逻辑（如多个词的组合、词的排除等）时。详细解释一下搜索引擎如何使用倒排索引来处理查询：
倒排索引查询的核心概念
- 倒排索引结构：
- 对于每个词（token），都有一个关联的文档列表，这个列表通常是按文档编号排序的。
- 每个文档在列表中可能还会有附加信息，如词频、位置信息等。
- 处理查询：
- 单词查询：对于单个词的查询，搜索引擎直接返回该词的倒排列表。
- 多词交集查询：对于包含多个词的查询，搜索引擎找到每个词的倒排列表，然后计算这些列表的交集。 这个交集代表了所有查询词都出现的文档集合。
- 复杂逻辑处理：对于包含逻辑运算（AND, OR, NOT）的查询，搜索引擎会结合使用集合的 交集（AND）、并集（OR）和差集（NOT）操作来处理查询。特别是在处理 NOT 逻辑时， 它并不是去查找那些未出现词的文档集合，而是从已经确定的结果集中排除含有这个词的文档。
更贴近实际搜索引擎的处理实现，如下：
python
import sys
input = sys.stdin.read
data = input().split()
index = 0
N = int(data[index])
index += 1
word_documents = []
# 读取每个词的倒排索引
for _ in range(N):
ci = int(data[index])
index += 1
documents = sorted(map(int, data[index:index + ci]))
index += ci
word_documents.append(documents)
M = int(data[index])
index += 1
results = []
# 处理每个查询
for _ in range(M):
query = list(map(int, data[index:index + N]))
index += N
# 集合存储各词的文档集合（使用交集获取所有词都出现的文档）
included_docs = []
excluded_docs = set()
# 解析查询条件
for i in range(N):
if query[i] == 1:
included_docs.append(word_documents[i])
elif query[i] == -1:
excluded_docs.update(word_documents[i])
# 仅在有包含词时计算交集
if included_docs:
result_set = set(included_docs[0])
for docs in included_docs[1:]:
result_set.intersection_update(docs)
result_set.difference_update(excluded_docs)
final_docs = sorted(result_set)
results.append(" ".join(map(str, final_docs)) if final_docs else "NOT FOUND")
else:
results.append("NOT FOUND")
# 输出所有查询结果
for result in results:
print(result)利用集合运算来处理倒排索引查询。思路如下：
建立倒排索引
对于每个词，读入出现该词的文档编号，将其存入一个集合中。处理查询
对于每个查询，按照查询向量（每个位置取值 1、-1、0）：- 对于标记为 1 的词（必须出现），求这些词对应集合的交集。
- 对于标记为 -1 的词（必须不出现），从交集中减去这些词出现的文档编号。
- 0 的词不作限制。
输出结果
将最终得到的候选文档集合按升序输出；如果为空，则输出 "NOT FOUND"。
下面是完整代码：
python
#!/usr/bin/env python3
import sys
def main():
data = sys.stdin.read().split()
it = iter(data)
# 读入倒排索引的词数
N = int(next(it))
inverted = []
for _ in range(N):
# 每个词的出现文档数
count = int(next(it))
docs = set()
for _ in range(count):
docs.add(int(next(it)))
inverted.append(docs)
# 读入查询数目
M = int(next(it))
output_lines = []
for _ in range(M):
# 每个查询包含 N 个数字
query = [int(next(it)) for _ in range(N)]
candidate = None
# 处理必须出现的词（值为 1）：取交集
for j in range(N):
if query[j] == 1:
if candidate is None:
candidate = inverted[j].copy()
else:
candidate &= inverted[j]
# 处理必须不出现的词（值为 -1）：从候选集合中剔除
for j in range(N):
if query[j] == -1:
candidate -= inverted[j]
# 输出结果
if candidate:
result_line = " ".join(map(str, sorted(candidate)))
output_lines.append(result_line)
else:
output_lines.append("NOT FOUND")
sys.stdout.write("\n".join(output_lines))
if __name__ == '__main__':
main()代码说明
倒排索引构建
从输入中读入每个词出现的文档编号，并用set保存，方便后续交并集操作。查询处理
- 先对所有标记为 1 的词取交集，即得到文档中同时包含所有这些词的候选集合。
- 再对所有标记为 -1 的词，从候选集合中减去这些文档编号。
- 0 表示不关心，不做任何操作。
输出
如果候选集合非空，则将文档编号排序后输出，否则输出 "NOT FOUND"。
python
n = int(input())
files = [] # 储存所有单词的文档归属数据
for i in range(n):
data = list(map(int,input().split()))
files.append(set(data[1:])) # 将每个单词对应的文档数据转化为集合，方便后续的操作
m = int(input())
for i in range(m):
data = list(map(int,input().split()))
t = data.index(1) # 第一个1要特殊处理，作为初始值
a = set(files[t]) # 所有有可能合题的文档（同样要储存在集合内）
for j in range(t + 1,n):
if data[j] == 1:
a = a & files[j] # 取交集（集合之间的∩、-、∪运算时间复杂度极低！）
b = set() # 所有一定不合题的文档（同样要储存在集合内）
for j in range(n):
if data[j] == -1:
b = b | files[j] # 取并集
# 注意：一定要先把所有要包含的文档全部放入a，所有不能包含的文档统一放入b，最后再a-b！
# 否则会损失一些b中的信息，例如如果是“无所谓、不能包含2、要包含12”，
# 如果一步一步使用交集和差集的话，则1和2都合题，这与第二个条件矛盾！因此不能一步一步来~
c = a - b # a与b的差集
finale = list(c)
if finale:
finale.sort()
print(" ".join(map(str,finale)))
else:print("NOT FOUND")python
n = int(input())
lis = []
all_documents = set()
# Read each word's document list
for _ in range(n):
data = list(map(int, input().split()))
doc_set = set(data[1:])
lis.append(doc_set)
all_documents.update(doc_set)
# Prepare the not-present sets 未出现文档集合
lis1 = [all_documents - doc_set for doc_set in lis]
# Read number of queries
m = int(input())
# Process each query
for _ in range(m):
query = list(map(int, input().split()))
result_set = None
# Determine result set based on requirements in query
for num, requirement in enumerate(query):
if requirement != 0:
current_set = lis[num] if requirement == 1 else lis1[num]
result_set = current_set if result_set is None else result_set.intersection(current_set)
if not result_set:
print("NOT FOUND")
else:
print(' '.join(map(str, sorted(result_set))))【王天纵 25地空学院】我写了个位运算的方法
python
from collections import defaultdict
n = int(input())
dd = defaultdict(int)
for i in range(n):
ls = set(input().split()[1:])
for s in ls:
dd[s] |= 1<<i
dd_res = defaultdict(list)
for k,v in dd.items():
dd_res[v].append(k)
m = int(input())
for _ in range(m):
q = input().split()
must1 = 0
must0 = 0
for i,s in enumerate(q):
if s=='1':
must1 |= 1<<i
elif s=='-1':
must0 |= 1<<i
res = []
for mask,docs in dd_res.items():
if (mask & must1) == must1 and (mask & must0) == 0:
res += docs
res = [str(x) for x in sorted(map(int,res))]
print(' '.join(res) if res else 'NOT FOUND')