如何高效在二维Python列表中查找指定词-文档配对是否存在

问题背景 #

现有如下Python列表数据：

data = [
    ['cat', 'doc_1.txt'],
    ['cat', 'doc_4.txt'],
    ['dog', 'doc_5.txt'],
    ['mouse', 'doc_6.txt'],
    ['horse', 'doc_7.txt']
]

需要快速回答类似"Does cat exist in doc_1.txt"的布尔查询，当前用嵌套循环实现效率低下，寻求更优方案。

高效解决方案：构建哈希索引 #

方案1：构建「文档→术语集合」映射 #

把每个文档对应的术语存入集合（集合的成员查询是O(1)时间复杂度），后续查询直接检查术语是否在对应文档的集合中：

# 构建索引
doc_terms = {}
for term, doc in data:
    if doc not in doc_terms:
        doc_terms[doc] = set()
    doc_terms[doc].add(term)

# 查询函数
def check_term_in_doc(term, doc):
    return term in doc_terms.get(doc, set())

# 测试示例
print(check_term_in_doc('cat', 'doc_1.txt'))  # 输出: True
print(check_term_in_doc('mouse', 'doc_1.txt'))  # 输出: False

方案2：构建「术语→文档集合」映射 #

如果查询场景更偏向“某个术语存在于哪些文档”，也可以反过来构建索引，同样支持快速查询：

# 构建索引
term_docs = {}
for term, doc in data:
    if term not in term_docs:
        term_docs[term] = set()
    term_docs[term].add(doc)

# 查询函数
def check_term_in_doc(term, doc):
    return doc in term_docs.get(term, set())

# 测试示例
print(check_term_in_doc('cat', 'doc_1.txt'))  # 输出: True
print(check_term_in_doc('mouse', 'doc_1.txt'))  # 输出: False

效率说明 #

嵌套循环的查询时间复杂度是O(n)（n为数据总条数），而基于哈希集合的查询是O(1)，仅需一次哈希查找就能得到结果，数据量越大，效率提升越明显。

内容的提问来源于stack exchange，提问作者jaykio77