在做文本去重任务时其实有很多中方法可供选择，譬如，对文章分词，两两对比词集合的jaccard系数，但是当遇到大规模文本去重时，这种方法的效率就太低了，接下来介绍一种大规模文本去重算法minhash。
什么是minhash？
什么是minhash呢，他跟传统的hash算法有什么区别呢，要理解这个问题，我们就要是知道hash是什么，简单理解hash就是将不同长度规则的文本转化成相同长度的字符串，用这些相同长度的字符串来表示原文本。但是传统hash存在一个问题是，相同内容的文本会生成相同的hash，但是相似的文本(可能就是一个字的差别)生成的hash会有很大的不同。但是我们在做文本相似度时，希望对相似的文本生成相似的hash，这样我们只需要计算一个个特定长度的hash值之间相似度，就可以近似得到原文本之间的相似度了，显然传统的hash算法是做不到这一点的。
怎么生成hash？
针对这个问题我们就要设计一种hash算法，让相似的文本生成相似的hash值。那在minhash算法中是怎么生成hash的呢？
假设我们这里有三个文本(假设a、b、c、d是四个不同的词):
S1 = abcd
S2 = bcd
S3 = ad
我们用一个特征矩阵来表示比较直观一点：
可以用如下3步来简单理解如何生成hash：
1)将行随机打乱。
2)行打乱后，针对每个S1、S2、S3看第一个1所在的行号，这个行号就是这个集合的最小哈希值。
3)设定hash的大小，如果是N，则重复上述步骤，随机进行N次行打乱，得到N个最小哈希值，那么这N个最小哈希值组成的集合就是S1、S2、S3对应的哈希签名。
为什么要进行行变换使用第一个1所在的行号作为最小哈希值呢，这样生成的哈希有什么意义呢？
我的理解是，这近似于一种抽样方法，用少数的哈希值来代替原本稀疏的特征矩阵，至于用第一个1所在的行号作为最小哈希的原因在于行号一样的集合原本的特征值都是1，这样得到哈希值也是一样，那么两个相似的文本得到的哈希在很大程度上就具有相似性，即解决了传统的hash算法存在的相似文本得到差别很大的哈希的问题。
我们直接看例子：
基于上述的矩阵，我们进行第一次行变换得到如下新矩阵(行号从0开始算)：
那么对于S1来说，顺着行号往下走，发现第一个1所在的行号是0，那么h(S1) = 0，依次类推，h(S2) = 0， h(S3) = 2。
第二次行变换：
h(S1) = 0，h(S2) = 1，h(S3) = 0
第三次行变换：
h(S1) = 0，h(S2) = 0，h(S3) = 1
假设我们就进行三次行变换及N为3(N通常要远远小于特征矩阵的行数)，我们就得到了3个最小哈希值，每个集合对应的哈希值可以表示如下(h里边的1,2,3分别代表对应的第几次行变换)：
怎么计算相似度？
从表中可以看出来，我们将原本的S1=abcd 转化成了[0,0,0]，S2=bcd转化成了[0,1,0]，S2=ad转化成了{2,0,1}。
我们现在已经将文本进行了hash编码，那么我们接下来就要计算哈希签名的相似度了，相似度的计算方法是对应位置相同的元素个数比上哈希签名长度。则：
Sim(S1,S2) = 2/3
Sim(S1,S3) = 1/3
Sim(S2,S3) = 0
以上就是minhash的计算过程，可能你要问了，一般情况下，特征矩阵有很多行，对特征矩阵进行打乱很耗时，特别是还要进行多次打乱，怎么办呢？
所以一般在工程中会定义一些函数，用这些函数算出来的值来作为最小哈希签名，在这里就不做过多介绍了，大家有时间也可以看看minhash的实现源码，加深理解minhash算法。
那么可能有要问了，使用minhash也只不过是把长文本用较短的hash编码来表示，不还是需要两两进行相似度计算嘛，别急，后边会写关于局部敏感哈希算法(LSH)来解决这个问题，更快速的进行文本去重。
