MinHash集合指纹 | Codeboy's Blog

形式陈述

一个随机次序，供所有集合共同使用

固定有限键宇宙 $U$ ，大小为 $N$ 。从它的全部 $N!$ 个排列中等概率抽取一个，记键 x 在其中的名次为 $r_\pi(x)\in\{1,\ldots,N\}$ 。先固定输入集合，再抽随机排列；讨论两个或更多集合时，全部集合使用同一份排列。

对非空 $A\subseteq U$ ，定义指纹为最靠前的原键

h_\pi(A)=\arg\min_{x\in A}r_\pi(x).

排列保证名次互异，所以最小键唯一。也可以保存该键的完整排列名次；因为排列是单射，两种表示的相等判断等价。空集使用不属于 U 的专用符号 $\bot$ 。

对两个集合，Jaccard相似度定义为

J(A,B)=\frac{|A\cap B|}{|A\cup B|}\quad(A\cup B\ne\varnothing), \qquad J(\varnothing,\varnothing)=1.

MinHash的碰撞等式是

\Pr_\pi(h_\pi(A)=h_\pi(B))=J(A,B).

这是关于完整随机排列的精确概率，不是说一次指纹能输出相似度的精确数值。[1, §3，Theorem 1的单样本情形]

多副本估计与误差

取 q 个相互独立的排列，q 为正整数。每个副本内部仍让 A、B 共享排列。令 $X_j=\mathbf1\{h_{\pi_j}(A)=h_{\pi_j}(B)\}$ ，输出

\widehat J=\frac1q\sum_{j=1}^qX_j, \qquad \mathbb E\widehat J=J, \qquad \operatorname{Var}(\widehat J)=\frac{J(1-J)}q.

由Hoeffding不等式，对 $\varepsilon>0$ ，

\Pr(|\widehat J-J|\ge\varepsilon)\le2e^{-2q\varepsilon^2}.

因此 $q\ge\lceil\log(2/\delta)/(2\varepsilon^2)\rceil$ 足以把失败概率控制在 $\delta\in(0,1)$ 。这同时说明两种相反的共享规则：集合之间应协调随机次序，估计副本之间应独立。

直觉

碰撞由并集的第一名决定

把 $A\cup B$ 按随机次序排成一队，观察第一名 x。若 x 在交集中，它在 A、B 都没有更早的竞争者，两份指纹都等于 x。反过来，如果两份指纹同为 x，那么 x 必在交集；若并集另有更早的 y，y 至少属于 A、B 中一个，那个集合就不会选 x。

所以“指纹相同”等价于“并集第一名属于交集”。均匀排列下，并集每个键成为第一名的概率都是 $1/|A\cup B|$ 。将交集各键的互斥事件相加，立即得到碰撞等式。证明只问谁排第一，不需要知道全部交集成员，也不需要把输入集合随机化。

流式计算只保留当前最小者

一个副本从 best = None 开始。每读一个键 x，计算它的固定名次；若它比目前名次小，就替换 best。处理任意前缀后的不变量是：best 为该前缀出现过的所有不同键中的最小名次键。新键只可能保留原最小者或自己成为最小者，归纳便闭合。

同一键重复一千次，名次仍相同，不改变结果。这里甚至不需要保存一个全局去重集合。若每次出现都重抽随机数，重复越多的键就有越多次争夺最小值的机会，统计对象会变成出现位置，而不再是不同键的集合。

例子与边界

同样的交集，排列不同就给出不同指纹

令 $A=\{0,1,2\}$ 、 $B=\{1,2,3\}$ ，则 J 为 $2/4=1/2$ 。若排列从小到大是 $0,1,2,3$ ，两指纹为0和1，不碰撞。若次序为 $2,0,3,1$ ，两者都选2。并集四个键各有 $1/4$ 机会成为第一名，只有1、2会使指纹相同。

对这个四键宇宙，枚举全部24个排列，恰有12个碰撞。这是一个可完整复算的概率空间。把第一个排列的“不碰撞”重复记录100次，只会得到100个相同的零，不能伪装成100个独立样本。

集合各抽各的排列会破坏目标

若 $A=B=\{0,1\}$ ，真实 J 为1。两个集合独立抽排列时，各自以 $1/2$ 选0或1，指纹相同概率却只有 $1/2$ 。错误不在估计公式，而在两侧没有使用同一个随机实验。

两空集的指纹都是 $\bot$ ，碰撞率1；一空一非空永不碰撞。若将 $\bot$ 编码成某个合法键或名次，空集就可能与真正含该键的集合错误相同。

两键均匀不够保证多键第一名均匀

在 $\{0,1,2,3,4\}$ 上取 $\pi_{a,b}(x)=(ax+b)\bmod5$ ，其中 $a\in\{1,2,3,4\}$ 、 $b\in\{0,\ldots,4\}$ 等概率，共20个排列。任意两个不同键的像均匀分布在20个有序不同值对上，但这不等于独立均匀哈希值，也不等于任意集合最小键均匀。

对集合 $\{0,1,2\}$ ，逐项枚举20个排列，0、1、2成为最小像的次数分别是7、6、7。若 $A=\{0\}$ 、 $B=\{0,1,2\}$ ，碰撞概率为 $7/20$ ，不同于 $J=1/3$ 。要求的是适用于整个并集的最小值对称性，不能只用键对性质替代。

短哈希值有并列时，按原键确定性破并列可使程序可重复，却不会自动恢复均匀第一名。例如所有哈希值都为零，按键排序就退化为固定最小键。若先把不同原键映射成同一短指纹再丢掉原键，估计的还是被合并后的集合，误差来源又多了一层。[1, §4.1]

推论与应用

成本与随机源是两份账

若名次查询、键比较、存取都按常数成本计算，长度为 L 的键流用 q 副本需 $O(qL+q)$ 时间及 $O(q)$ 个摘要记录；空流仍须初始化 q 个空指纹。比较两个摘要需 $O(q)$ 时间。保留的是原键，键很长时还应计入读取、规范化、保存与比较的实际成本。

本页的精确参考实现把整个有限排列存为数组，公共随机源另占 $O(N)$ 空间、构建需 $O(N)$ 时间；q 份完整排列占 $O(qN)$ 。它不是“小种子就能无条件生成任意均匀排列”的算法。用伪随机函数或受限哈希族替代时，应另外声明最小值偏差、碰撞和随机模型，不能把摘要的 $O(q)$ 偷换成整个系统的空间。

LSH放大候选索引把共享排列指纹用于检索：每张表拼接多个独立分量，再对多张表的桶取并集，按记录ID去重并核验原始Jaccard条件。基础碰撞率仍由本页保证；表间独立性、元组键和随机源的存储，以及出现预算截断导致的额外漏检，都必须另行核算，不能从单对相似度估计自动推出。

从一个最小者转向固定容量集合样本

若想用同一个排列保留多个不同键，并在分片间去重合并，Bottom-k摘要保留前 k 名，再用并集样本中的交集比例估计 J。那 k 个键来自一次无放回抽样，不能当作 q 个独立MinHash副本照抄方差公式。

若键带有非负实权，普通MinHash仍只看“是否出现”。一致加权抽样将每个坐标扩成相应高度的区间，目标改为最小权重和除以最大权重和。定义目标之后再选指纹，才能区分重复去重、频次权重与相似度。

共享随机键终结任务要求交出排列、两侧指纹、逐副本碰撞和一个失效随机族的精确计数，而不是只报一个相似度小数。

参考资料

[1] Andrei Z. Broder，On the Resemblance and Containment of Documents，Compression and Complexity of Sequences，1997，§§2–3、§4.1。原论文在集合化的文档特征上给出共同排列抽样；本页独立展开单样本等价事件、空集约定、仿射族反例和副本成本。

形式陈述 ​

一个随机次序，供所有集合共同使用 ​

多副本估计与误差 ​

碰撞由并集的第一名决定 ​

流式计算只保留当前最小者 ​

同样的交集，排列不同就给出不同指纹 ​

集合各抽各的排列会破坏目标 ​

两键均匀不够保证多键第一名均匀 ​

成本与随机源是两份账 ​

从一个最小者转向固定容量集合样本 ​

反向链接