# 作业四

# 习题 4.2

• 因为只使用一个哈希函数，同一哈希函数，输入值相同，则哈希值也一定相同，故被分为 k 组时，每组实际都为平行且独立互不干扰，因此只关注一组内的情况即可

假设哈希函数的选择是完全随机的

此时误判率为插入$m$ 个元素后，某元素被判断为在集合内，实际不在集合内的概率

将$n$ 位内存分为$k$ 组，每组$\frac n k$​位

那么，任意一次哈希函数选中这一位的概率为

$$\frac k n$$

因此没有选择这一位的概率为

$$1-\frac k n$$

当$m$ 个元素被同一哈希函数哈希到数组内后，设$X_i$ 为数组第$i$ 位的值

$$P(X_i =0)=(1- \frac k n)^m \approx e^{- \frac {km} n}$$

由此可知，插入$m$ 个元素后，某一位被置为 1 的概率为

$$P(X_i = 1)=1-P(X_i=0)\approx 1-e^{- \frac {km} n}$$

因为只有一个哈希函数，因此该位恰好被置为 1 就会发生误判，那么误判率为

$$f = 1-e^{- \frac {km} n}$$

• 区别：使用单个哈希函数和使用多个哈希函数相比，可能会导致更高的误判率，并且分 k 组实际上减小了空间利用率，因为每组内的情况是完全平行的

# 习题 4.3

分析内存

$$4 GB=4*1024KB=4*1024*1024B\\ 4GB/64B=65536$$

显然远小于我们需要分析的数据量，因此需要进行分治

1. 划分小文件：

$$5Billion*64B=305Kilo\ GB \\ 305Kilo\ GB\ / \ 1000= 305MB$$

• 首先，遍历文件 a，对遍历到的 URL 计算哈希值 hash(URL) % 1000 。
• 根据计算结果，将遍历到的 URL 存储到 a0, a1, a2, …, a999 这 1000 个小文件中，每个小文件大小约为 305MB。
• 使用相同的方法遍历文件 b，将文件 b 中的 URL 分别存储到 b0, b1, b2, …, b999 这 1000 个小文件中。

2. 查找共同的 URL：

• 所有可能相同的 URL 都在对应的小文件中，即 a0 对应 b0, a1 对应 b1, …, a999 对应 b999。
• 我们只需求出这 1000 对小文件中相同的 URL。
• 遍历每个小文件 ai (i ∈ [0, 999]) 中的所有 URL，将 URL 存储到一个 HashSet 集合中。
• 然后遍历文件 bi 中的每个 URL，检查是否在 HashSet 集合中存在。若存在，说明这是共同的 URL，可以将其保存到一个单独的文件中。

# 习题 4.4

令集合分别为 A B C

$$A = \{1,2,3,4\} \\ B = \{2,3,5,7\}\\ C = \{2,4,6\}$$

则

$$Jaccard(A,B)=\frac 2 6 =\frac 1 3\\ Jaccard(A,C)=\frac 2 5\\ Jaccard(B,C)=\frac 1 6$$

# 习题 4.7

假设有两个集合 A 和 B，且它们的 Jaccard 相似度为 0，即 $J(A, B) = 0$。证明 Min-Hashing 可以给出正确的估计。

证明：

• 由于 $J(A, B) = 0$，说明 A 和 B 没有共同的元素，即 $A \cap B = \emptyset$

• 对于任意一个哈希函数，它在 A 和 B 中的元素都不相同，则集合 A B 所构成的特征矩阵，没有两行值均为 1 的情况，只有两行值有且仅有一个值为 1, 或者全为 0 的情况

  行号	A	B
  0	0	1
  1	1	0
  $\cdots$	$\cdots$	$\cdots$
  n	0	0

• 故集合 A B 的最小哈希值一定不同，因此 Min-Hash 签名的每一列都不同。

• 由于 Min-Hash 签名的每一列都不同，它们的相似度为 1，即 $J_{\text{Min-Hash}}(A, B) = 1$

• 因此，Min-Hashing 正确地估计了 A 和 B 的相似度。

# 习题 4.8

显然：

• $\widehat {JS}(S_1,S_2)$ 表示通过随机排列$h_i$ 计算的$Jaccard$ 相似度的估计值
• $JS(S_1,S_2)$ 表示$S_1$ 和$S_2$ 的真实$Jaccard$​相似度

1. $Hoeffding$​不等式：

   • 对于独立同分布的随机变量$X_1,X_2,...,X_k$，满足$0 \leq X_i \leq 1$, 以及$E[X_i]=p$，有

     $$P(|\frac 1 k \sum\limits_{i=1}^k X_i-p|>\epsilon)\leq 2e^{-2k\epsilon^2}$$

   • 需要估计$|\widehat {JS}(S_1,S_2) - JS(S_1,S_2)|$, 令$p = JS(S_1,S_2)$, 则$E[X_i] = p$

   • 根据$Hoeffding$ 不等式，有：

     $$P(|\widehat {JS}(S_1,S_2) - JS(S_1,S_2)| > \epsilon) \leq 2e^{-2k\epsilon^2}$$

2. 选择$k$ 的条件

   • 需要证明

     $$P(|\widehat {JS}(S_1,S_2) - JS(S_1,S_2)| > \epsilon JS(S_1,S_2)) < \delta$$

   • 因此，有$2e^{-2k\epsilon^2} < \delta$

   • 解得：$k> \frac {ln(1/ \delta)}{2 \epsilon^2}$​

   • 因此，当$k = O(\frac {ln(1/ \delta)}{\epsilon^2})$ 时，上述概率小于$\delta$

# 习题 4.9

(1)

$$Jaccard(S_1,S_2)=\frac 1 4\\ Jaccard(S_1,S_3)=\frac 1 4\\ Jaccard(S_2,S_3)=0$$

(2)

$$mh_1(S_1)=1,mh_1(S_2)=1,mh_1(S_3)=4\\ mh_2(S_1)=0,mh_2(S_2)=1,mh_2(S_3)=4\\ mh_3(S_1)=0,mh_3(S_2)=1,mh_3(S_3)=4$$

# 习题 4.11

• 假定将某个最小哈希签名矩阵划分为$b$ 组，每组为$r$ 行，并且假定两个集合的$Jaccard$ 相似度为$s$

• 由定理 4.1 可知，两个集合最小哈希值相等的概率为$s$

1. 在某个具体的组中，这对集合所有的最小哈希值都相等的概率是$s^r$​

2. 在某个具体的组中，这对集合至少有一个位置的最小哈希值不相等的概率是$1 - s^r$，即没有被映射到同一个桶

3. 在任何一个组中，这对集合都没有被映射到同一个桶中的概率是$(1-s^r)^b$​

4. 在整个最小哈希签名矩阵中，至少在一个组中两个集合被映射到同一个桶概率为$1-(1-s^r)^b$

   因此当$1-(1-s^r)^b=\frac 1 2$ 时，解得$s= (1-(\frac 1 2)^{\frac 1 b})^{\frac 1 r} \approx (\frac 1 b)^{\frac 1 r}$​

   即，

$$t= (1-(\frac 1 2)^{\frac 1 b})^{\frac 1 r} \approx (\frac 1 b)^{\frac 1 r}$$