这里先详细讲一下最小哈希签名的由来。
首先是集合的矩阵表示：
这叫做集合的特征矩阵，矩阵不同的列对应不同的集合，所有的行对应全集，如果r行中的元素存在于列c对应的集合中，那该位置就为1，否则为0，当然特征矩阵只是便于理解，并非真正的数据存储方式。
然后开始讲最小哈希，想这样一种情况，我们知道所有的行对应全集，给定一种哈希函数，如果从上到下，全集元素的排列顺序与元素哈希值从小到大的顺序相同，那是不是对于每个集合，也即每个列，从上到下，所找到的第一个1，就是该集合所有元素中，哈希结果最小的那个，也就是这种哈希函数下，该列的最小哈希。
那如果对上面的过程进行M次，也即选择M种不同的哈希函数，那我们就能得到一个M行的最小哈希签名矩阵，不同列对应不同集合，不同行对应不同的哈希函数，每个位置就是列对应的集合在行对应的哈希函数下的最小哈希。
当然我们不用对每个哈希函数，都将全集排一次序，只要始终记录最小值即可。
然后有了最小哈希签名矩阵，我们就可以依此来计算Jaccard相似度了，需要注意的是，通过最小哈希签名矩阵计算出来的Jaccard相似度，只是真实Jaccard相似度的估计值（但如果两列真实Jaccard相似度为0，那最小哈希签名矩阵总能估计出正确的结果）。
然后介绍文档的局部敏感哈希算法（Locality-Sensitive Hashing，LSH）
如果文档数量过大，即便是利用最小哈希签名矩阵的方式可以将大文档压缩成小的签名并同时保持文档对之间的预期相似度，计算起来仍然非常困难。当然，如果我们一定要计算每对文档的相似度，即便采用分布式计算的方法减少实耗时间，总计算量也是不会减少的。不过，如果我们只需要得到那些相似度超过某个下界的文档，采用LSH，就可以降低计算量，提高计算速度。
LSH的一个一般性做法是对目标项进行多次哈希处理，使得相似项会比不相似项更可能哈希到同一桶中。然后将至少有一次哈希到同一桶中的文档看成是候选对，我们只会检查候选对之前的相似度。
《浅谈搜索引擎基础》中讲过SimHash，SimHash在最后比较的那一步，就采用了LSH的思想，就像里面讲过的，将原串四等分，分组聚类，聚类其实基本等价于哈希到桶，这样就可以减少需要比较的文档数目。
LSH也可以应用于目标项的最小哈希签名矩阵，思路与SimHash类似。如果我们拥有目标项的最小哈希签名函数，那么一个有效的哈希处理方法是将签名矩阵划分成b个行条，也就是分成b部分，每个行条由r行组成。对每个行条，存在一个哈希函数能够将行条中的每r个整数组成的列向量映射到某个大数目范围的桶中，对不同行条我们使用独立的b个桶，不会出现不同行条哈希到同一个桶中的情况。
