所谓集合的相似性就是说，对于集合A和集合B（当然，这两个集合是随意的），我们可通过某种方式来比较这两个集合是否具有一些相同的特征和联系，并从中得知这二者相似的百分比有多大。
当然，相似性也包括了相同，这就好比正方形属于矩形一样。如果两个集合相同的话，那么他们之间相似的百分比就是100了。
本文将分别解析集合相同与相似这两部分，尤其是判断相同，我将会用代码和图例来说明。
第一节 判断集合是否相同
判定两个集合是否相同，举个例子：现有串A = “总书记 军委主席 国家主席”，和串B = “国家主席 军委主席 总书记”，我们将串A和串B看做集合A和集合B，从两个集合的内容我们看到它们是相同的，只是顺序不同而已。（附注：对于很短的词串，我们可以自己通过统计来做判断，但是集合中如果有大量的词串，人工统计的方法显然是不可取的）。
那我们能通过哪些方法来判定集合是否相同呢？通过复杂度的改进，我将介绍四种方法。
方法一：逐个比较法
这种方法太容易想到了：假设集合A和集合B中的元素个数均为N，那么只需对集合中的元素一一作比较，这样的话复杂度为O(N * N)，即用两个for语句就可以搞定了！这种解法可以说是最笨的算法了。代码滤过！
方法二：排序法
首先，对两集合先分别做排序，然后在进行比较。做排序可以用快速排序，复杂度为O(N * LogN)，作比较需O(N)，综合下来O(N * LogN) + O(N)
---> O(N * LogN)。显然，这比方法一提高了一些。不过这离我们想要达到的效果还是有距离的！
说到这，额外说几句。在最近的写的几篇博文中都涉及到了排序算法（不过很惭愧，每篇博客发表的周期大概都在一个月左右），而涉及到排序算法的时候，我们一般都会首选快速排序，其次是堆排序和归并了。那么我在这套用JULY的一句话：“你能在三十分钟内很清晰的讲解出快速排序算法，并很准确的写出来吗”？很多人说这没有意义，背下来不就写出来了，但是别忘了，还要求你清晰的讲解它。这就要求我们不仅能写出来，而且更要理解它、掌握它。这不禁使我想起前辈吴军在《数学之美》里说的：技术分为道和术，做事的方法是术，做事的原理和原则是道！我们在学习的过程中不仅要学会“术”，更要慢慢掌握“道”。
方法三：哈希映射
关于哈希方面的知识我就不罗嗦了！首先，我们将其中任意一个集合映射到一张哈希表中，当然这张哈希表的大小为O(N)。然后将另一个集合的元素一一与哈希表中的元素作比较，如果全部匹配，那么就说明这两个集合时相同的。此时，我们分析一下，创建一张哈希表需O(N)的空间，作比较需O(N)的时间，感觉哈希算法还是很不错的，都在线性的范围内解决。唯一让我们觉得遗憾的是需要O(N)的空间，那么有没有办法在不占用空间的前提下，在线性时间内判断集合相同的问题呢？答案是肯定的！
给出法三的代码之前，给个图例：
char * HashMapping(char *Set, char *HashTable, int Set_Size)
{
/*** Set：为将要产生指纹的集合
*** HashTable: 映射产生的hash表
*** Set_Size: 为集合的大小
***/
for(int i = 0; i < Set_Size; i++)
{
HashTable <-- hash(Set[i]);
}
return HashTable;
}
bool HashCompared(char *HashTable, char *ComparedSet, int Set_Size)
{
/*** HashTable为由集合已经产生的hash表
*** ComparedSet为比较的集合
***/
for(int i = 0; i < Set_Size; i++)
{
if(HashTable(hash(Set_B[i])) == Set_B[i])
{
continue;
}
else
{
return false;
}
}
return true;
}
方法四：指纹识别法
我们知道，人的指纹几乎是唯一的，发生相同的概率是及其微小的。于是我们可将此种思想引入到判定集合是否相同的问题。具体的想法是：如果两个集合是相同的，那么这两个集合所产生的指纹必定是相同的，即使集合里子串的顺序是不相同的，也没关系（根据交换律）。
我们定义一集合S = {e1, e2, e3, … , en}的指纹FP(S) = FP(e1) + FP(e2) + … + FP(en)，其中FP(e1)，FP(e2), … , FP(en)分别为S中这些元素对应的指纹。于是，不同的集合所产生的指纹就不一样，相同的集合所长生的指纹必定一致。当然，也会出现不同的集合产生相同指纹的情况，但是这种情况发生的概率是非常小的，每一千八百亿亿次才出现一次，我们可认为发生的概率为0。
通过介绍指纹识别算法，我们看到它的复杂度为O(N)，而且不需要额外的空间，我们很满意这样的结果。
同法三一样，给出代码之前，给个图例：
char * FingerPrint(char *Set, char *FP, int Set_Size)
{
/*** Set：为将要产生指纹的集合
*** FP：为将要产生的指纹
*** Set_Num:为集合的大小
***/
for(int i = 0; i < Set_Num; i++)
{
FP[i] = handle(Set[i]);
FP += FP[i];
}
return FP;
}
bool CompareSet(char *FP_A, char *FP_B)
{
return FP_A && FP_B ? TRUE:FALSE;
}
第二节 判断集合相似性
说起相似性，我们可能会立刻想到第一节讲的相同，的确，相似和相同的关系就好比正方形和矩形的关系一样。其实，相似的情况在学习和生活中很常见，比如，我们中学时学的相似三角形；一对双胞胎长的有多像；两篇文章中相同内容的百分比有多大等等。这些都是相似性的问题。
那我们是怎样来判断两个集合之间的相似性呢？我们还是利用相同的思想，只不过是如果两个集合相同的话，它们之间的相似性为百分之百罢了；如果不相同的话，只是介于百分之零到百分之一百之间（前闭后开区间，即[0，100)）。
Ok，我们来看看解决的办法。
方法一：逐个比较法（同第一节法一）
对两个集合中的每个子串进行一次彻头彻尾的比较。
方法二：特征词提取法
对两个集合彻头彻尾的比较，如果两篇文章篇幅都很大，这显然是很慢的。于是就有了特征词提取法。该方法的思想是：在集合中提取与主题中心思想有关联的一些特征词，之后对这些特征词进行比较。如果这些特征词相似度达到80%或者90%或者其它，我们就说这两篇文章是相似的。
因此，这种方法的关键就在特征词的选取了。前面已经说过，一定要选择和主题联系大的词。我们可以用TF-IDF算法来提取集合中的特征词，而IDF越大的词鉴别能力越强，所以我们只需找到IDF最大的一些词，来比较它们的相似度，进而就能得到两个集合是否相似。
方法三：分治法 + 特征词提取法
该方法相比于法二增加了分治的思想，即我们可将一个大的集合分成一些小的集合，然后分别对这些小的集合进行特征词提取法，完成之后，再对这些小集合进行比较就能判断这两个大集合是否相似。利用这种方法，我们就能判断文章之间的抄袭问题。
好了，以上就是解决集合相似度的几种方法。在相似度这节，我没有给出相关的代码，主要还是想学习算法的思想，再加上相同和相似在某些方面是一致的，第二节讲的也比较详细，所以不再赘述。
第三节 结束语
想想、写写、画画......