海量短文本场景下的去重算法

在大多数情况下，大量的重复文本一般不会是什么好事情，比如互相抄袭的新闻，群发的垃圾短信，铺天盖地的广告文案等，这些都会造成网络内容的同质化并加重数据库的存储负担，更糟糕的是降低了文本内容的质量。因此需要一种准确而高效率的文本 去重算法。而最朴素的做法就是将所有文本进行两两比较，简单易理解，最符合人类的直觉，对于少量文本来说，实现起来也很方便，但是对于海量文本来说，这明显是行不通的，因为它的时间复杂度是，针对亿级别的文本去重时，时间消耗可能就要以年为单位，此路不通。

另外，我们讲到去重，实际上暗含了两个方面的内容，第一是用什么方式去比较更为高效，第二是比较的时候去重标准是什么。这里的去重标准在文本领域来说，就是如何度量两个文本的相似性，通常包含编辑距离，Jaccard距离，cosine距离，欧氏距离，语义距离等等，在不同领域和场景下选用不同的相似性度量方法，这里不是本文的重点，所以按下不表，下面着重解决如何进行高效率比较的问题。

降低时间复杂度的关键： > 尽力将潜在的相似文本聚合到一块，从而大大缩小需要比较的范围

海量文本去重算法里面，最为知名的就是simHash算法，是谷歌提出来的一套算法，并被应用到实际的网页去重中。 simHash算法的最大特点是：将文本映射为一个01串，并且相似文本之间得到的01串也是相似的，只在少数几个位置上的0和1不一样。为了表征原始文本的相似度，可以计算两个01串之间在多少个位置上不同，这便是汉明距离，用来表征simHash算法下两个文本之间的相似度，通常来说，越相似的文本，对应simHash映射得到的01串之间的汉明距离越小。

为了让这个过程更为清晰，这里举个简单的例子。

t1 = “妈妈喊你来吃饭” t2 = “妈妈叫你来吃饭”

可以看到，上面这两个字符串虽然只有一个字不同，但是通过简单的Hash算法得到的hash值可能就完全不一样了，因而无法利用得到的hash值来表征原始文本的相似性。然而通过simHash算法的映射后，得到的simHash值便是如下这样：

SH1 = “1000010010101101[1]1111110000010101101000[0]00111110000100101[1]001011” SH2 = “1000010010101101[0]1111110000010101101000[1]00111110000100101[0]001011”

仔细观察，上面的两个simHash值只有三个地方不一样（不一样的地方用”[]”标出），因此原始文本之间的汉明距离便是3。通常来说，用于相似文本检测中的汉明距离判断标准就是3，也就是说，当两个文本对应的simHash之间的汉明距离小于或等于3，则认为这两个文本为相似，如果是要去重的话，就只能留下其中一个。

simHash算法的去重过程思路很简单，首先有一个关键点： > 假如相似文本判断标准为汉明距离3，在一个待去重语料集中存在两个相似文本，那也就是说这两个相似文本之间的汉明距离最大值为3（对应hash值最多有3个地方不同），如果simHash为64位，可以将这个64位的hash值从高位到低位，划分成四个连续的16位，那么这3个不同的位置最多只能填满4个中的任意3个区间（可以反过来想，如果这4个区间都填满了，那就变成汉明距离为4了）。也就是说两个相似文本必定在其中的一个连续16位上完全一致。

想明白了这个关键点之后，就可以对整个待去重文本都进行一次simHash映射（本文中使用64位举例），接着将这些01串从高位到低位均分成四段，按照上面的讨论，两个相似的文本一定会有其中一段一样，仍用上面的例子，分成的四段如下所示：

t1 = “妈妈喊你来吃饭” SH1 = “1000010010101101[1]1111110000010101101000[0]00111110000100101[1]001011” SH1_1 = “1000010010101101” #第一段 SH1_2 = “[1]111111000001010” #第二段 SH1_3 = “1101000[0]00111110” #第三段 SH1_4 = “000100101[1]001011” #第四段

t2 = “妈妈叫你来吃饭” SH2 = “1000010010101101[0]1111110000010101101000[1]00111110000100101[0]001011” SH2_1 = “1000010010101101” #第一段 SH2_2 = “[0]111111000001010” #第二段 SH2_3 = “1101000[1]00111110” #第三段 SH2_4 = “000100101[0]001011” #第四段

这一步做完之后，接下来就是索引的建立。按照上面的讨论，每一个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（如果是词和字层面的，对应shingles）的方法，直接从原始文本上滑动窗口截取，也可以去掉停用词后在剩下的有序词组合中截取，还可以对原始文本进行摘要生成后再截取，总之只要是基于原始文本或可接受范围内的有损文本，都可以利用类似的思想来产生这些作为索引的子串。

整个去重算法分为五个大的框架，分别包括：文本预处理，倒排索引的建立，并行化分治，去重算法的实现，文本归并等。

文本预处理根据所选用的具体子串截取方法的不同，而有所不同。如果子串是由词组合形成的，则需要对文本进行分词，如果需要去掉停用词，那么这也是文本预处理的工作。为了简化过程的分析，这里主要以原始文本直接截取子串为例，因此预处理的工作相对偏少一些。

假定潜在的两个相似文本（要求去重后其中一个被去掉）分别是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比较，分别从时间复杂度和去重准确度上来说，

首先，时间复杂度大大降低 – 分桶的个数根据文本量的大小动态变化，大约为文本数的2倍，平均单个桶内不到一条文本，桶内的计算复杂度大大降低；而simHash算法中，桶的个数是固定的4*216=26万个 – 一般来说，只有相似文本才有相似的词组合，所以某个特定的词组合下相似文本占大多数，单个桶内的去重时间复杂度倾向于O(N)；相应的，simHash单个桶内依然有很多不相似文本，去重时间复杂度倾向于O(N^2)

其次，相似性的度量更为精准： – 可以使用更为精准的相似性度量工具，但是simHash的汉明距离在短文本里面行不通，召回太低，很多相似文本并不满足汉明距离小于3的条件

这里提出的基于文本局部信息的去重算法，是在短文本场景下simHash等去重算法无法满足去重目的而提出的，实际上，同样也可以应用于长文本下的去重要求，理论上，时间复杂度可以比simHash低很多，效果能够和simHash差不多，唯一的缺点是存储空间会大一些，因为算法要求存储很多个文本的副本，但在存储这些文本的副本时候，可以使用全局唯一的id来代替，所以存储压力并不会提升很多，相比时间复杂度的大大降低，这点空间存储压力是完全可以承担的。

来原：腾讯QQ 大数据