【算法优化】记一次不太成功的文本相似性去重_腾讯云代理,腾讯云代理商,腾讯云优惠折扣-深圳航网科技有限公司

公司新闻

行业新闻

专业知识

【算法优化】记一次不太成功的文本相似性去重

| 2019-05-17

0、背景

在我们舆情分析系统里，有一个功能是文章搜索，返回相似性去重后的文章，这里比较耗时的是一个相似性去重的功能，就是在返回的数据集里将相似的文章去掉。

如果只是去重也还好，关键是还要进行分页，这就意味着需要计算去重后的总数。

1、原来的方案

对每一篇文章循环处理，用文章的simhash值去ES查找相似的文章ID，然后从剩余的集合里去掉这些ID，这样处理完成之后，就会得到一个去重完之后的数据集。

我一看这里，这样那行呀，要是原始数据集有一万篇文章，这个功能的极端情况就得查询一万次ES！平均可能也得查询5000次，这难怪要几分钟才出结果了，而且ES也难受呀。

赶紧指导同事进行优化吧。

2、第一个优化版本

因为输入数据集里，每个文章的simhash值已经是算好了的，那我们完全可以不查ES，而直接计算两个向量的距离呀。于是把算法的思路跟同事说清楚，其实也很简单，就是对于每个文章，直接和后面的文章相比较，如果相似度达到我们的阈值，则从集合中剔除。

同事蹭蹭蹭用三重循环的纯python就实现了，迫不及待想看到奇迹，上线测试环境，刷新。。。好久好久都没有出结果。以为是其他问题影响了，再刷新一次，还是一样。

看到日志里打印的初始集合的文章数量，大概1.7万，瞬间明白了，因为这个过滤算法的时间复杂度是N平方，这得算好几亿次相似度。。。不慢也不行呀！

3、第二个优化版本

我还是不死心，因为一次查询要查询几千次ES，就这想怎么优化效果都是有限的，也无法达到客户的预期，别说秒级了，想降到一分钟以下都不容易。

用纯python写，需要三重循环，这些循环能否转为矩阵运算呢？

显然是可以的，于是不死心的自己直接实现了一个版本：

print(len(data))
start = time.time()
new_data = []
for item in data:
    simhash, article_id = list(item['simhash']), item['id']
    # 不足64位的前面补0，文章id放到第一个值
    new_data.append([article_id] + ['0']*(64-len(simhash)) + simhash)

np_data = np.array(new_data)
print(np_data.shape)

thr = 0.85 * 64
results = []
while np_data.shape[0] > 1:
    curr_row = np_data[0]
    np_data = np_data[1:]
    counts = np.count_nonzero(curr_row == np_data, axis=1)
    results.append((curr_row[0], np_data[counts > thr].shape[0] + 1))
    np_data = np_data[counts <= thr]

if len(np_data) > 0:
    results.append((np_data[0][0], 1))

for item in results:
    print(item)
print('time: ', time.time() - start, ' len: ', len(results))

思路跟纯python的其实是一样的，只是将里面的两重循环转成了矩阵运算，充分利用numpy的特性。

在一个1.7k的测试集上效果是可以的，本机测试只要0.4秒左右，比原来使用ES要快，关键是还不用占用宝贵的ES资源。

但是如果数据量更大行不行呢？于是简单的将输入数据重复了10次（这犯了一个错误），效果还是很快，1秒以下，让人满意。

奇迹要来了的幸福就在眼前。

然而，现实的打脸来得太快，一万多的数据一跑，loading标志就在那里一直转呀转。。。转了10多分钟才停下来！

我不得不仔细想一想，这中间发生了什么？ES的几千次查询都比你快？

其实就算矩阵运算再快，那也得现算，而ES中的simhash是经过特殊处理的，有底层的倒排索引支撑，找相似的时候并不需要在全局里搜索（相当于提前剪枝）。

当数据集数量大于一定值时，基于ES倒排索引的提前剪枝的效率就体现出来的。当然，这个算法也不是一无是处，当数据量比较小的时候，这个算法可以比ES更高效。

4、总结

做算法优化，不能头脑发热撸起袖子就干，而是要先考虑清楚算法的时间复杂度和空间复杂度，如果多想一想，其实第一个版本的优化根本不会发生。

结合ES的特性来考虑，第二种情况的结果应该也是可以预见的。

后面还比较了很多聚类的算法，其实情况都类似，再好聚类算法也需要现算，这就避免不了时间延迟的问题，还不如用原来的方案。

在写这个文章的时候，就这个问题想到，算法最耗时的其实是要计算去重后的文章总数用于分页，但是这个分页是否真的是必须存在的呢？

我觉得这并不一定是要存在的，去重后的总数其实也并没有太多的作用，只要知道是否还有下一页就可以了。如果这个客户可以接受（在这个功能上，我觉得做一点小取舍，换来性能的大提升完全是非常值得的），这个时间延迟马上就能降到百毫秒的级别。

所以，解决问题并不能总是想着技术手段，有时非技术手段更直接有效。

编辑：航网科技来源：腾讯云本文版权归原作者所有转载请注明出处

关注我们

微信扫一扫关注我们