如何用倒排索引查找重叠字典并减少比较？

2026-11-04数据阿明

结论

倒排索引可以缩小候选范围，但不保证所有输入都比 O(n^2) 快。假设有 n 个字典，每个字典有 k 个键。要判断一对字典是否重叠，需要逐键检查列表是否相同，或是否至少包含一个共同元素。如果大量字典的每个键上都有共同元素，那么所有字典对都可能重叠。此时输出本身就有 n(n-1)/2 对，任何算法都至少需要花费与输出量成正比的时间。

用倒排索引生成候选对

对每个键和列表元素，记录包含该元素的字典编号。处理一个字典时，先在每个键上合并其列表元素对应的编号集合，再对各键的集合取交集。交集里的编号，就是在每个键上都满足条件的字典。

如果某个键的列表为空，只有另一个字典在该键上的列表也为空时，两者才兼容。代码会单独记录空列表对应的字典编号。非空列表则无论完全相同，还是只有部分元素相同，都可以通过倒排索引找到。

下面的实现要求列表元素可哈希，例如字符串、数字和布尔值：

from collections import defaultdict


def find_overlapping_pairs(dictionaries):
    if not dictionaries:
        return []

    keys = list(dictionaries[0])
    postings = {key: defaultdict(set) for key in keys}
    empty_lists = {key: set() for key in keys}

    # 建立倒排索引：每个键、每个元素对应包含它的字典编号。
    for dict_id, dictionary in enumerate(dictionaries):
        for key in keys:
            values = dictionary[key]
            if not values:
                empty_lists[key].add(dict_id)
                continue

            for value in set(values):
                postings[key][value].add(dict_id)

    pairs = []

    for dict_id, dictionary in enumerate(dictionaries):
        candidates = None

        for key in keys:
            values = dictionary[key]

            if values:
                compatible = set()
                for value in set(values):
                    compatible.update(postings[key].get(value, ()))
            else:
                compatible = empty_lists[key]

            if candidates is None:
                candidates = set(compatible)
            else:
                candidates.intersection_update(compatible)

            if not candidates:
                break

        if candidates:
            # 只保留编号更大的字典，避免重复输出和与自身配对。
            pairs.extend((dict_id, other_id)
                         for other_id in candidates
                         if other_id > dict_id)

    return pairs

用题目中的示例，字典 1 和 3 会成为候选对，因为它们在 a、b 的列表中都有共同元素，c 的列表也都包含 "x"。字典 1 和 2 则会在 b 上被排除，因为 [True] 与 [False] 没有共同元素。

复杂度与适用条件

令 S 表示所有列表元素的总数。建立索引通常需要 O(S) 时间。之后的耗时取决于倒排集合的大小、候选交集的规模和最终配对数量。如果每个元素只出现在少数字典中，候选集合通常较小，可以省去逐对检查。若某些常见元素几乎出现在所有字典中，中间集合和结果仍可能达到 O(n^2) 规模。

排序后只比较相邻字典并不能保证普遍有效。能否提速取决于数据分布和结果规模。如果列表元素不可哈希，就不能直接使用上面的字典索引，需要先为元素定义稳定的哈希键，或改用逐项比较。后一种做法可能更慢。