最朴素的做法
大量的重复文本通常不太好。 例如，互相模仿的新闻、群发的垃圾邮件、铺天盖地的广告文案等等。 这些都会导致互联网内容的同质化和数据库的存储负担，更糟的是会降低文本内容的质量。 因此，需要一种准确高效的文本重计算算法。 最朴素的方法是比较所有的文本两个，两个。 简单易懂，最适合人类的直觉。 对少量文本来说也很有用，但对大量文本来说显然是不可能的。 之所以这么说，是因为时间的复杂性，如果加重亿级的文本，时间的消耗就有可能以年为单位。
另外，我们说要重视的，实际上包括两个方面的内容。 第一是用什么方法比较更有效率，第二是比较时重视的标准是什么？ 这里的事实标准是指在文本区域中如何测量两个文本的相似性，通常包括编辑距离、Jaccard距离、cosine距离、欧几里得距离、语义距离等，根据区域和场景而不同
核心思想
降低时间复杂性的关键：将潜在的相似文本放在一起，大大缩小了比较范围
sim混列算法
在海量的文本删除算法中，最有名的是simHash算法，是谷歌提出的一组算法，应用于实际的网页删除。 simHash算法的最大特点是将文本映射到一个01字符串，相似文本之间得到的01字符串也很相似，只有很少的位置0和1不同。 为了表示原始文本的相似度，可以计算两个01字符串之间的不同位置。 这就是汉明距离，用于表示simHash算法中两个文本之间的相似度。 通常，越相似的文本，对应于simHash映射得到的01个字符串之间的汉明距离越小。
为了更清楚这个过程，我在这里举个简单的例子。
t1='妈妈来吃饭'
t2='妈妈来吃饭'
可以看出，虽然上面的两个字符串只相差一个字符，但通过简单的哈希算法得到的哈希值可能完全不同，不能用得到的哈希值来表示原始文本的相似性。 但是，通过sim混列算法的映射，所得到的sim混列值如下
sh1=' 1000100101101 [1] 11111000010101101101000 [0] 001111000101 [1] 001011 '
sh2=' 1000100101101 [0] 111111000010101101101000 [1] 001111000101 [0] 001011 '
如果仔细观察，由于上面的两个simHash值只在三个地方不同(不同之处为) )来表示)，所以原始文本之间的汉明距离为3。 通常，用于相似文本检测的汉明距离的判断标准为3。 也就是说，如果两个文本对应的simHash之间的汉明距离小于或等于3，则认为这两个文本相似，如果文本变重，则只剩下其中一个。
simHash算法锐化过程的思路很简单，首先有一个关键。 如果相似文本的判断标准为汉明距离3，而一个锐化蒙版中存在两个相似文本，也就是说，两个相似文本之间的汉明距离的最大值为3。 如果simHash为64位，则将这64位散列值划分为4个连续的16位，这些16位可以从高到低变化，则这三个不同的位置最多只能填充4个中的任意3个区间(相反，如果填充了这4个区间，则为哈哈) 也就是说，两个类似文本一定在其中一个连续的16位上完全一致。
了解了这个重点后，可以对要删除的整个文本进行一次simHash映射，然后将这01个字符串从上到下分为四个段落。 根据上述讨论，两个相似的文本一定有其中之一，但使用上述例子，将其分为以下四个段落。
t1='妈妈来吃饭'
sh1=' 1000100101101 [1] 11111000010101101101000 [0] 001111000101 [1] 001011 '
SH1_1='1000010010101101' #第一段
sh1 _2=' [1]第111111000001010 ' #段
SH1_3='1101000[0]00111110' #第三段
SH1_4='000100101[1]001011' #第4段
t2='妈妈来吃饭'
sh2=' 1000100101101 [0] 111111000010101101101000 [1] 001111000101 [0] 001011 '
SH2_1='1000010010101101' #第一段
sh2 _2=' [0]第111111000001010 ' #段
SH2_3='1101000[1]00111110' #第三段
SH2_4='000100101[0]001011' #第4段
这个步骤结束后，接下来是索引的创建。 根据上述讨论，各simHash从上位到下位分为4个区段，各区段为16位。 在创建倒排索引的过程中，将这些切出的16位01列的片段分别作为索引的key值，在对应的位置具有该切片
段的所有文本添加到这个索引的value域中。 直观上理解，首先有四个大桶，分别是1,2,3,4号（对应的是64位hash值中的第一、二、三、四段），在每一个大桶中，又分别有个小桶，这些小桶的编号从0000000000000000到1111111111111111.在建立索引时，每一个文本得到对应的simHash值后，分别去考察每一段（确定是1,2,3和4中的哪个大桶），再根据该段中的16位hash值，将文本放置到对应大桶中对应编号的小桶中。 索引建立好后，由于相似文本一定会存在于某一个16位hash值的桶中，因此针对这些分段的所有桶进行去重（可以并行做），便可以将文本集合中的所有相似文本去掉。整个利用simHash进行去重的过程如下图所示：
总结一下，整个simHash去重的步骤主要是三个： 1. 针对每一个待去重文本进行simHash映射； 2. 将simHash值分段建立倒排索引； 3. 在每一个分段的hash值中并行化去重操作。
利用simHash进行去重有两个点非常关键： - simHash映射后仍然保持了原始文本的相似性； - 分而治之的思想大大降低了不必要的比较次数。
因此，有了这两点做保证，对于长文本下的simHash算法以及使用汉明距离来度量文本之间的相似性，可以极大降低算法的时间复杂度，并且也能取得很好的去重效果。但是在短文本场景下，这种度量方法的效果将会变得很差，通常情况下，用来度量长文本相似的汉明距离阈值为3，但是短文本中，相似文本之间的汉明距离通常是大于3的，并且该算法中，基于汉明距离的相似性阈值选取的越高，该算法的时间复杂度也会越高，此时汉明距离无法继续作为短文本相似性的度量标准应用到短文本去重中。
基于文本局部信息的去重算法
基于文本局部信息的去重过程，其基本思想和simHash类似，只不过不是利用hash值，而是直接利用文本的一个子串作为key,然后凡是拥有这个子串的文本都会被放入到这个子串对应的桶中。 这里隐含了一个前提： > 任意两个可判定的相似文本，必定在一个或多个子串上是完全一致的。
此外，子串的产生，可以通过类似于n-grams（如果是词和字层面的，对应慈祥的睫毛）的方法，直接从原始文本上滑动窗口截取，也可以去掉停用词后在剩下的有序词组合中截取，还可以对原始文本进行摘要生成后再截取，总之只要是基于原始文本或可接受范围内的有损文本，都可以利用类似的思想来产生这些作为索引的子串。
整个去重算法分为五个大的框架，分别包括：文本预处理，倒排索引的建立，并行化分治，去重算法的实现，文本归并等。
文本预处理
文本预处理根据所选用的具体子串截取方法的不同，而有所不同。如果子串是由词组合形成的，则需要对文本进行分词，如果需要去掉停用词，那么这也是文本预处理的工作。为了简化过程的分析，这里主要以原始文本直接截取子串为例，因此预处理的工作相对偏少一些。
倒排索引的建立
假定潜在的两个相似文本（要求去重后其中一个被去掉）分别是t1和t2，二者之间完全一致的最大连续子文本串有k个，它们组成一个集合，将其定义为S = {s1,s2,...,sk}，这些子文本串的长度也对应一个集合L = {l1,l2,...,lk}，针对该特定的两个文本进行去重时，所选择的截取子文本串长度不能超过某一个阈值，因为如果截取长度超过了该阈值，这两个文本便不再会拥有同一个子文本串的索引，因而算法自始至终都不会去比较这两个文本，从而无法达到去重的目的。这个阈值便被定义为这两个文本上的最清爽的航空去重长度，有：
在所有的全局文本上去重的话，相应的也有一个全局去重长度m，它表征了如果要将这部分全局文本中的相似文本进行去重的话，针对每一个文本需要选取一个合适的截取长度。一般来说，全局去重长度的选择跟去重率和算法的时间复杂度相关，实际选择的时候，都是去重率和时间复杂度的折中考虑。全局去重长度选择的越小，文本的去重效果越好（去重率会增大），但相应的时间复杂度也越高。全局去重长度选择越大，相似文本去重的效果变差（部分相似文本不会得到比较），但时间复杂度会降低。这里的原因是：如果全局去重长度选择的过高，就会大于很多相似文本的最清爽的航空去重长度，因而这些相似文本便不再会判定为相似文本，去重率因而会下降，但也正是因为比较次数减少，时间复杂度会降低。相反，随着全局去重长度的减小，更多的相似文本会划分到同一个索引下，经过相似度计算之后，相应的相似文本也会被去除掉，因而全局的去重率会上升，但是由于比较次数增多，时间复杂度会增大。
假定有一个从真实文本中抽样出来的相似文本集C，可以根据这个样例集来决定全局去重长度m，实际情况表明，通常来说当m>=4（一般对应两个中文词的长度），算法并行计算的时候，时间复杂度已经降低到可以接受的范围，因此可以得到：
假定某个待去重的文本t，其长度为n。定义S为截取的m-gram子串的集合，根据m和n的大小关系，有下列两种情况： （1）当n>=m时，可以按照m的大小截取出一些m-gram子串的集合，该集合的大小为n-m+1，用符号表示为S = {s1,s2,...,sn-m+1}； （2）当n<m时，无法截取长度为m的子串，因此将整个文本作为一个整体加入到子串集合当中，因此有S={t}. 每一个待去重文本的m-gram子串集合生成之后，针对每个文本t，遍历对应集合中的元素，将该集合中的每一个子串作为key，原始文本t作为对应value组合成一个key-value对。所有文本的m-gram子串集合遍历结束后，便可以得到每一个文本与其n-m+1个m-gram子串的倒排索引。 接下来，按照索引key值的不同，可以将同一个索引key值下的所有文本进行聚合，以便进行去重逻辑的实现。
算法的并行框架
这里的并行框架主要依托于Spark来实现，原始的文本集合以HDFS的形式存储在集群的各个节点上，将这些文本按照上面所讲的方法将每一个文本划分到对应的索引下之后，以每一个索引作为key进行hash，并根据hash值将所有待去重文本分配到相应的机器节点（下图中的Server），分布式集群中的每一个工作节点只需负责本机器下的去重工作。基于Spark的分布式框架如下，每一个Server便是一个工作节点，Driver负责分发和调配，将以HDFS存储形式的文本集合分发到这些节点上，相当于将潜在的可能重复文本进行一次粗粒度的各自聚合，不重复的文本已经被完全分割开，因而每个Server只需要负责该节点上的去重工作即可，最终每个Server中留下的便是初次去重之后的文本。
去重的实现
并行化框架建立后，可以针对划分到每一个索引下的文本进行两两比较（如上一个图所示，每一个Server有可能处理多个索引对应的文本），从而做到文本去重。根据1中的分析，任意两个可判定的相似文本t1和t2，必定在一个或多个子文本串上是完全一致的。根据3.1.1中的设定，这些完全一致的最大连续子串组成了一个集合S = {s1,s2,...,sk}，针对t1和t2划分m-gram子串的过程中，假定可以分别得到m-gram子串的集合为S1和S2，不妨假设S中有一个子串为si，它的长度|si|大于全局去重长度m，那么一定可以将该子串si划分为|si|-m+1个m-gram子串，并且这些子串一定会既存在于S1中，也会存在于S2中。更进一步，t1和t2都会同时出现在以这|si|-m+1个m-gram子串为key的倒排索引中。
去重的时候，针对每一个索引下的所有文本，可以计算两两之间的相似性。具体的做法是，动态维护一个结果集，初始状态下随机从该索引下的文本中选取一条作为种子文本，随后遍历该索引下的待去重文本，尝试将遍历到的每一条文本加入结果集中，在添加的过程中，计算该遍历到的文本与结果集中的每一条文本是否可以判定为相似（利用相似性度量的阈值），如果与结果集中某条文本达到了相似的条件，则退出结果集的遍历，如果结果集中完全遍历仍未触发相似条件，则表明此次待去重的文本和已知结果集中没有任何重复，因此将该文本添加到结果集中，并开始待去重文本的下一次遍历。 去重的时候，两个文本之间的相似性度量非常关键，直接影响到去重的效果。可以使用的方法包括编辑距离、Jaccard相似度等等。在实际使用时，Jaccard相似度的计算一般要求将待比较的文本进行分词，假定两个待比较的文本分词后的集合分别为A和B，那么按照Jaccard相似度的定义可以得到这两个文本的相似度 显然，两个完全不一致的文本其Jaccard相似度为0，相反两个完全一样的文本其Jaccard相似度为1，因此Jaccard相似度是一个介于0和1之间的数，去重的时候，可以根据实际需要决定一个合适的阈值，大于该阈值的都将被判定为相似文本从而被去掉。
整个的去重实现伪代码如下：
初始状态：
文本集合T = {t_1,t_2,...,t_n}
去重结果R = {}
相似度阈值sim_th
输出结果：
去重结果R
算法过程：
for i in T:
flag = true
for j in R:
if( similarity(i,j) < sim_th )
flag = false
break -> next i
else
continue -> next j
if( flag )
R.append(i) #表示i文本和当前结果集中的任意文本都不重复，则将i添加到结果集中
文本归并去重
这一个步骤的主要目的是将分处在各个不同机器节点上的文本按照预先编排好的id，重新进行一次普通的hash去重，因为根据上一步的过程中，可能在不同子串对应的桶中会留下同一个文本，这一步经过hash去重后，便将这些重复的id去除掉。 最终得到的结果便是，在整个文本集上，所有的重复文本都只保留了一条，完成了去重的目的。整个的去重流程如下图所示：
和simHash进行比较
这里提出来的去重算法与simHash比较，分别从时间复杂度和去重准确度上来说，
首先，时间复杂度大大降低 - 分桶的个数根据文本量的大小动态变化，大约为文本数的2倍，平均单个桶内不到一条文本，桶内的计算复杂度大大降低；而simHash算法中，桶的个数是固定的4*216=26万个 - 一般来说，只有相似文本才有相似的词组合，所以某个特定的词组合下相似文本占大多数，单个桶内的去重时间复杂度倾向于O(N)；相应的，simHash单个桶内依然有很多不相似文本，去重时间复杂度倾向于O(N^2)
其次，相似性的度量更为精准： - 可以使用更为精准的相似性度量工具，但是simHash的汉明距离在短文本里面行不通，召回太低，很多相似文本并不满足汉明距离小于3的条件
总结
这里提出的基于文本局部信息的去重算法，是在短文本场景下simHash等去重算法无法满足去重目的而提出的，实际上，同样也可以应用于长文本下的去重要求，理论上，时间复杂度可以比simHash低很多，效果能够和simHash差不多，唯一的缺点是存储空间会大一些，因为算法要求存储很多个文本的副本，但在存储这些文本的副本时候，可以使用全局唯一的id来代替，所以存储压力并不会提升很多，相比时间复杂度的大大降低，这点空间存储压力是完全可以承担的。
原文发布于微信公众号 - 腾讯QQ大数据（qq_bigdata）