本发明涉及文本去重领域，尤其涉及一种海量短文本自适应分桶的反向去重方法。
背景技术：
海量短文本相似度去重是一个广泛而基础的问题，在实际应用中需要兼顾方法的效率和准确率。
网络上热点新闻的转载率很高，新闻量百万级别存在大量重复的新闻标题。去重的时候，往往需要两两比较相似度，时间复杂度是随数据量指数级上升的，所以一般方法是优先进行数据分桶，分而治之，再在每个桶内进行相似度去重得到不重复的结果，最后进行合并。分桶主要有主题分类、文本子串、局部敏感hash值三种。
专利号cn107025218a：一种文本去重方法和装置就是利用文本子串进行数据分桶，在每个桶内两两比较相似度得到不重复的结果，最后进行合并。本发明比该方案的分桶策略以及去重策略都有了很大的提升。
现有技术有两个主要缺点：
1、文本子串分桶策略虽然划分了数据集，但是总体的数据可能达到几十倍，很难避免数据倾斜，简单来说就是说某些文本子串出现频次过高，导致一些桶内数据过多，影响总体去重效率。
2、一条文本由于有多个文本子串，会出现在多个桶内。如果它在有些桶内被去重了，但是在某个桶没有被去重，由于每个桶保留的是不重复的结果，那么这条数据依赖会出现在最后合并的结果中。
举个例子：
t1:国盛金控：子公司国盛证券、国盛期货领导层被接管答记者问
t2:国盛金控：子公司国盛证券、国盛期货被接管了
t3:总理答记者问传递“大国自信”
上面三条数据都是真实数据,t1和t2根据子串“国盛证券”分到一个桶内，去重后剩下t2,而t1和t3根据“答记者问”分到同一个桶内，去重后剩下t1和t3，最后合并结果的时候t1,t2,t3都保留了。实际上，t1和t2应该只保留一条数据，但是在第一个桶内去重的时候无法预知该保留哪个结果，如果保留了t2，那就会出现三条数据都没有被去重的情况。
正因为如此，本发明对该方案的分桶策略以及去重策略都做了重大改进。
分桶策略上采用基于分段的simhash值作为特征序列进行数据分桶，对某些数据量达到一定阈值的分桶进一步根据随机后缀划分成固定基数内的分桶，大大改善了数据倾斜的情况。
去重策略上是使每个桶内排序靠后的数据被去重，然后被去重的数据合并到一起，最后在全量数据里面剔除被去重的数据得到去重后的结果。这样可以确保每个被去重过的数据都不会被遗漏。
技术实现要素：
本发明目的在于针对现有技术的不足，提出一种海量短文本自适应分桶的反向去重方法，可以通过并行计算提升去重的效率，通过反向去重和特征词比对提升最终结果的准确率。
本发明的目的是通过以下技术方案来实现的：一种海量短文本自适应分桶的反向去重方法，该方法包括以下步骤：
(1)对全量数据进行自适应分桶；具体为：对全量数据计算每条数据的simhash特征码，分为n段；
记所述特征码为s，则
其中concat表示字符串拼接，si表示特征码s的第i个片段，其代表的数据记为(i,si)，统计(i,si)在全量数据中的频率，频率在一定阈值t以内的数据分到一个桶内，频率在一定阈值t以上的数据计算随机整数：
其中t0为小于阈值t的整数，ceil表示向上取整，计算随机整数后的数据记为(i,si,randint)，将频率在一定阈值t以上的数据分到
(2)对每个桶内的数据进行排序，去重时将排序靠后的数据去重，对排序后的数据进行两两比较，根据相似度判断两个数据之间是高度相似、相似还是不相似，不相似的数据不被去重，相似的数据直接被去重，高度相似的数据比较特征子串，将特征子串一样的去重。具体分组过程是结合具体领域的文本数据，调整余弦相似度和编辑距离相似度的范围，使重复数据比例在需求的范围内：具体分成如下三中情况：
a.高度相似：分组内95％以上的数据属于重复数据，需要结合特征子串进一步判断；
b.相似：分组内85％以上的数据属于重复数据；
c.不相似：分组内85％以下的数据属于重复数据；
(3)合并各个桶被去重的数据，从全量数据中剔除被去重的数据得到去重的全量数据。
进一步地，每个桶内的数据根据时间、数据来源、md5值等信息进行排序。
进一步地，相似度判断具体如下：
根据预训练的词向量计算余弦相似度：
similarity1＝cosine(v1,v2)
其中cosine为余弦函数，v1,v2为单位词向量，similarity1的范围是0-1，越靠近1相似度越高。
根据字符串的编辑距离计算编辑距离相似度：
其中a，b为两个字符串，ed表示编辑距离函数，表示两个字符串要达到相同需要增加、删除和修改的字符数量之和，len表示字符串长度函数，max表示取最大值函数，similarity2的范围也是0-1，越靠近1相似度越高。
进一步地，自适应分桶可以通过主题词、文本类别、文本字串、局部敏感hash分段等组合的多级分桶来实现。
本发明的有益效果：
(1)基于simhash的自适应分桶策略在由于固定的特征64位特征码和分段数，可以在数据总量上远远低于传统技术的文本子串的方法，可以在保证尽可能将相似的数据分到一个桶的情况下有效避免数据倾斜。
(2)反向去重方法解决了同一个桶内本应该被去重的数据遗漏的情况。
(3)相似度和特征字符串结合去重的方法是现有技术没有涉及到的，特别是在新闻标题领域，可以有效提升去重的准确率，避免不重复的数据被错误去重。
附图说明
图1为待处理文本根据simhash特征码和随机数被分到n个分桶内的流程图；
图2为各个分桶内分别结合相似度和特征子串去重排序靠后的文本的流程图。
具体实施方式
以下结合附图对本发明具体实施方式作进一步详细说明。
如图1和图2所示，本发明提供的一种海量短文本自适应分桶的反向去重方法，具体步骤如下：
step1：对全量数据进行自适应分桶；自适应分桶可以通过主题词、文本类别、文本字串、局部敏感hash分段等组合的多级分桶来实现。
step2：对每个桶内的数据进行排序，根据相似度和特征子串结合的两两比较获取被去重的数据
step3：合并各个桶被去重的数据，从全量数据中剔除被去重的数据得到去重的全量数据
每一步的详细阐述：
step1详述：
对全量数据计算每条数据的64位simhash特征码，分为n段，其中8>＝n>4，(simhash算法本质是一种局部敏感hash算法)
记所述特征码为s,则
其中t0为小于t的整数，ceil表示向上取整，根据(i,si,randint)将频率在一定阈值t以上的数据分到
step2详述：
a.对每个桶内的数据根据时间、数据来源、md5值(一种根据字符串生成固定长度加密序列的算法)等信息进行排序，这个是反向去重的必要条件，因为这样如果两条重复的数据同时分到两个一样的桶内，排序可以保证总是排序靠后的数据被去重，本发明中被去重均表示去重排序靠后的数据。b.对排序后的数据进行两两比较，根据预训练的词向量计算余弦相似度，
similarity1＝cosine(v1,v2)
其中cosine为余弦函数，v1,v2为单位词向量，similarity1的范围是0-1，越靠近1相似度越高。
根据字符串的编辑距离计算编辑距离相似度：
其中a，b为两个字符串，ed表示编辑距离函数，表示两个字符串要达到相同需要增加、删除和修改的字符数量之和，len表示字符串长度函数，max表示取最大值函数，similarity2的范围也是0-1，越靠近1相似度越高。
计算结果分为高度相似、相似、不相似三类，不相似的数据不被去重，相似的数据直接被去重，高度相似的数据需要比较特征子串，将特征子串一样的才被去重。
具体分组过程是结合具体领域的文本数据，调整余弦相似度和编辑距离相似度的范围，使重复数据比例在需求的范围内：具体分成如下三中情况：
a.高度相似：分组内95％以上的数据属于重复数据，需要结合特征子串进一步判断；
b.相似：分组内85％以上的数据属于重复数据；
c.不相似：分组内85％以下的数据属于重复数据；
特征子串是一些量词、日期等特殊子串，比较“2020年第三季度浙江省杭州市经济数据”和“2020年第四季度浙江省杭州市经济数据”的余弦相似度很高，但逻辑上属于不重复的数据。提取特征子串(2020年，第三季度)和(2020年，第四季度)不一致，所以不被去重。
step3详述：
合并每个桶内被去重的数据，对重复被去重的数据进行去重得到集合k，最后从全量数据里面剔除k得到去重后的全量数据。
上述实施例用来解释说明本发明，而不是对本发明进行限制，在本发明的精神和权利要求的保护范围内，对本发明作出的任何修改和改变，都落入本发明的保护范围。
1.一种海量短文本自适应分桶的反向去重方法，其特征在于，该方法包括以下步骤：
(1)对全量数据进行自适应分桶；具体为：对全量数据计算每条数据的simhash特征码，分为n段；
记所述特征码为s，则
其中concat表示字符串拼接，si表示特征码s的第i个片段，其代表的数据记为(i,si)，统计(i,si)在全量数据中的频率，频率在一定阈值t以内的数据分到一个桶内，频率在一定阈值t以上的数据计算随机整数：
其中t0为小于阈值t的整数，ceil表示向上取整，计算随机整数后的数据记为(i,si,randint)，将频率在一定阈值t以上的数据分到
(2)对每个桶内的数据进行排序，去重时将排序靠后的数据去重，对排序后的数据进行两两比较，根据相似度判断两个数据之间是高度相似、相似还是不相似，不相似的数据不被去重，相似的数据直接被去重，高度相似的数据比较特征子串，将特征子串一样的去重。具体分组过程是结合具体领域的文本数据，调整余弦相似度和编辑距离相似度的范围，使重复数据比例在需求的范围内：具体分成如下三中情况：
a.高度相似：分组内95％以上的数据属于重复数据，需要结合特征子串进一步判断；
b.相似：分组内85％以上的数据属于重复数据；
c.不相似：分组内85％以下的数据属于重复数据；
(3)合并各个桶被去重的数据，从全量数据中剔除被去重的数据得到去重的全量数据。
2.根据权利要求1所述的一种海量短文本自适应分桶的反向去重方法，其特征在于，每个桶内的数据根据时间、数据来源、md5值等信息进行排序。
3.根据权利要求1所述的一种海量短文本自适应分桶的反向去重方法，其特征在于，相似度判断具体如下：
根据预训练的词向量计算余弦相似度：
similarity1＝cosine(v1,v2)
其中cosine为余弦函数，v1,v2为单位词向量，similarity1的范围是0-1，越靠近1相似度越高。
根据字符串的编辑距离计算编辑距离相似度：
其中a，b为两个字符串，ed表示编辑距离函数，表示两个字符串要达到相同需要增加、删除和修改的字符数量之和，len表示字符串长度函数，max表示取最大值函数，similarity2的范围也是0-1，越靠近1相似度越高。
4.根据权利要求1所述的一种海量短文本自适应分桶的反向去重方法，其特征在于，自适应分桶可以通过主题词、文本类别、文本字串、局部敏感hash分段等组合的多级分桶来实现。
技术总结