稀疏相似度

难度: Hard

两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。

输入为一个二维数组 docs，docs[i] 表示 id 为 i 的文档。返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，其格式为 {id1},{id2}: {similarity}，其中 id1 为两个文档中较小的 id，similarity 为相似度，精确到小数点后 4 位。以任意顺序返回数组均可。

示例:

输入: 
[
  [14, 15, 100, 9, 3],
  [32, 1, 9, 3, 5],
  [15, 29, 2, 6, 8, 7],
  [7, 10]
]
输出:
[
  "0,1: 0.2500",
  "0,2: 0.1000",
  "2,3: 0.1429"
]

提示：

docs.length <= 500
docs[i].length <= 500

Submission

运行时间: 252 ms

内存: 47.4 MB

class Solution:
    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:
        len_map = [len(x) for x in docs]  # 每个doc的长度
        cnt = collections.defaultdict(list)  # 统计每个词在哪些字典里出现过
        sim_cnt = collections.defaultdict(int)  # key为(id1, id2)，val为交集元素数量
        for i, doc in enumerate(docs):
            for word in doc:
                if word in cnt.keys():
                    for prev in cnt[word]: # 计数。此时cnt里文档的编号都小于i，所以可以在遍历文档的时候顺便计数
                        sim_cnt[(prev, i)] += 1
                cnt[word].append(i)
        
        ans = ["" for _ in range(len(sim_cnt))]
        for i, (key, val) in enumerate(sim_cnt.items()):
            id1, id2 = key
            sim_score = val/(len_map[id1]+len_map[id2]-val)+1e-9  # 看评论区大佬说是浮点数精度问题
            ans[i] = f"{id1},{id2}: {sim_score:.4f}"
        return ans

Explain

本题解采用了倒排索引的思想。首先，统计每个文档的长度并存储在len_map中。然后，遍历每个文档中的每个词，利用cnt字典记录每个词出现在哪些文档中。在遍历的过程中，如果当前词在之前的文档中出现过，那么就更新sim_cnt字典，其中sim_cnt的键是文档对的元组(id1, id2)，值是这对文档的交集元素数量。最后，根据sim_cnt和len_map计算每对文档的相似度，并格式化输出。

时间复杂度: O(d^2n)

空间复杂度: O(dn + d^2)

import collections

class Solution:
    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:
        len_map = [len(x) for x in docs]  # 每个doc的长度
        cnt = collections.defaultdict(list)  # 统计每个词在哪些字典里出现过
        sim_cnt = collections.defaultdict(int)  # key为(id1, id2)，val为交集元素数量
        for i, doc in enumerate(docs):
            for word in doc:
                if word in cnt.keys():
                    for prev in cnt[word]: # 计数。此时cnt里文档的编号都小于i，所以可以在遍历文档的时候顺便计数
                        sim_cnt[(prev, i)] += 1
                cnt[word].append(i)
        
        ans = [\"\" for _ in range(len(sim_cnt))]
        for i, (key, val) in enumerate(sim_cnt.items()):
            id1, id2 = key
            sim_score = val/(len_map[id1]+len_map[id2]-val)+1e-9  # 看评论区大佬说是浮点数精度问题
            ans[i] = f\"{id1},{id2}: {sim_score:.4f}\"
        return ans

Explore

在构建倒排索引时，选择将每个词出现在哪些文档中的信息存储在`cnt`字典中是为了快速定位和计算文档间的相似度。记录每个词出现在哪些文档中可以直接用来求解文档对之间的交集数目，这是计算Jaccard相似度的关键步骤。如果存储其他信息，比如词频或文档中的位置，虽然可以提供更多细节，但对于计算文档间的相似度并不直接有用，且会增加额外的处理复杂度和空间消耗。

在算法中，维护一个`len_map`来记录每个文档的长度是为了在计算相似度时快速获取文档的长度信息，这是计算Jaccard相似度公式中所需的分母部分。这一步可以通过在遍历文档时即时计算长度并存储来实现，但使用`len_map`可以使得代码更清晰和高效，因为每个文档的长度只需要计算一次即可重复使用。如果不使用`len_map`，每次计算相似度时都需要重新计算文档长度，将增加计算负担。

在计算相似度时，添加`1e-9`是为了避免在Python中由于浮点数精度问题可能导致的除零错误或不稳定的数值表现。这个小的数值（称为epsilon）确保了分母不会为零，从而使得结果更稳定。对于结果的精度，这种处理通常影响极小，因为`1e-9`非常接近于零，其对最终相似度的影响通常低于实际精度需求，但可以在极端情况下防止程序错误。