在数据挖掘中，有一个比较基本的问题，就是比较两个集合的相似度。关于这个问题，最笨的方法就是用一个两重循环来遍历这两个集合中的所有元素，进而统计这两个集合中相同元素的个数。但是，当这两个集合里的元素数量非常庞大时，同时又有很多个集合需要判断两两之间的相似度时，这种方法就呵呵了，对内存和时间的消耗都非常大。因此，为了解决这个问题，数据挖掘中有另一个方法。

Jaccard相似度

在介绍具体算法之前，我们首先来了解一个概念：Jaccard相似度。

Jaccard相似度是用来描述两个集合间的相似度的，其计算方法如下（假设有两个集合A，B）：，也就是A与B交集的元素个数除以A与B并集的元素个数；为了书写方便，下面的讨论中我们将集合A和B的Jaccard相似度记为SIM(A,B)；

例如：上图中有两个集合A，B；A中有4个元素，B中有5个元素；A，B的交集元素个数为2，并集元素个数为7，所以SIM(A,B) = 2 / 7；

k-Shingle

       假如我们把一整篇文章看成一个长的字符串，那么k-shingle就是这篇文档中长度为k的任意字符子串。所以，一篇文章就是很多个不同的k-shingle的集合。

        例如：现在我们有一篇很短的文章，文章内容为abcdabd，令k=2