未分類
2 2 月 2021

分享：如何实现一个高效率的查重系统？顺带问问各位 V 友大牛有没有更好的实现方式

分享：如何实现一个高效率的查重系统？顺带问问各位 V 友大牛有没有更好的实现方式

資深大佬 : kwklover 2

因为最近做了个小项目，是一个站内查重系统(就是提交一个文档，判断这个文档与已有文档的重复率)，因为预算不多，所以我想了个简单的实现方式：
1，把待查重的文档的前 N 字（比如前 300 字），拆解为 10 个句子，分别去站内搜索，得出一个疑似重复度高的集合。
2，把疑似集合的前 N 字与待分析文档，分别建立字表做准确分析，得出重复率百分比。

这个项目，开发周期一周，检测效果还行，但就是效率有点慢，百来万的数据量，每一个文档的检测需要几秒，而且还不是全文比对，做个了折中，检测前 N 字的做法。

各位 V 友大牛有没有更好的实现方式？

大佬有話說 (28)

  • 資深大佬 : siyemiaokube

    随便 yy 了一下：
    词袋记录常见词，给站内文章打 tag，分别建索引

    然后把 input 随便剪一剪，分别词袋，根据 tag 对应的索引列表比对？

  • 資深大佬 : sampeng

    简单的向量相似性即可…

  • 資深大佬 : sampeng

    每个文档提交的时候酸一个向量值。查重就是比一下得事。应该飞快。比你查前 300 字，拆句，搜索快 n 倍。算法不超过 100 行代码

  • 資深大佬 : xuanbg

    根据关键词的权重计算向量

  • 資深大佬 : jeeyong

    jieba 分词, 把所有得词标号, 如果没有, 给一个新的.
    之后整篇文章获得一个类似[0, 25, 37, 178, 3578]得数组, 就是 2 说的向量了..
    后面不会了..谁来给我补补课..

  • 資深大佬 : neoblackcap

    snap 很多 bug，又不修。安装完系统第一件事就是卸装它

  • 資深大佬 : DoctorCat

    simhash

  • 資深大佬 : laminux29

    查重就没办法高效率，高效率的查重准确度不高。连谷歌处理这事都是砸钱去用空间换时间，没钱就只能消耗时间。

  • 資深大佬 : noqwerty

    比较简单的办法是每个文档算 TF-IDF，然后用文档间的 cosine similarity 判断相似程度

  • 資深大佬 : taowen

    https://twitter.com/slimsag/status/1360136379301199872 How do you check for existence of a key in a set with 100M keys, in only 125ns? Using Xor Filters

  • 主 資深大佬 : kwklover

    @sampeng
    向量的比较真的有那么高效？一百万多数据，先得建立一百多万的向量，然后每个文档与一百多万的向量做比较，效率真的能飞快？

    刚开始的时候，也从网上看过一些文章，比如谷歌工程师写的按余弦夹角理论。但感觉实现起来比较复杂啊。

    @jeeyong
    分词的方式，依赖词库的分词方式，往往不太准确，结果就差别很大了，效果未必准确，小样本下测试偏差较大，大样本下没做测试，最后改为不分词，直接比较字。

  • 主 資深大佬 : kwklover

    @jeeyong
    我也不是专业 NLP，如果建立向量速度快，比较速度快，倒是可以研究一下。
    通过搜索的方式+字表比较的方式也能解决问题，就是建立 Lucene 索引的过程也是很吃资源，很耗费时间的，不过就是搜索快。

  • 資深大佬 : ntest

    用 SimHash 比较吧，每个文档生成一次就行了

  • 主 資深大佬 : kwklover

    @ntest
    网上搜索了一下 SimHash 的资料，大概就是给每个文档建立一个 Hash，然后比较，所以比较的实现方式决定了最终的效率，不过 SimHash 可以计算出相似，但是具体相似多少，没法得出。

  • 資深大佬 : dream4ever

    吴军当年在谷歌黑板报上就写了相关的文章，印象中是用矩阵运算之类的方法解决的，感兴趣可以搜搜。

  • 資深大佬 : sampeng

    @kwklover 又不是没次都是建 100 万次…每次入的时候计算一次这个新文档而已，就是第一次慢

  • 資深大佬 : sampeng

    另外 ps…要测试速度很简单…做一百万次除法就是每次查重需要的时间和 cpu 消耗

  • 資深大佬 : jeeyong

    @kwklover 哈? 我一直默认你得需求属于小打小闹那种…哈哈哈…打扰了, 惹不起惹不起

  • 資深大佬 : AX5N

    这玩意是有算法的，建议去搜一下，不要自己想。

  • 主 資深大佬 : kwklover

    @jeeyong 不是默认，本来就是小打小闹的，欢迎大牛提供好的思路，目前的解决方案，解决百来万级的数据查重，勉强够用，再上一个量级，比如千万级数据量，那肯定慢死了，就是想征集一下不同的思路和方案。

  • 資深大佬 : dongxiao

    试试 Embedding+FAISS

  • 資深大佬 : igeeky

    可以试试 postgresql. psql 支持文本相似度查询排序. 可以看看这个网页: https://developer.aliyun.com/article/59212

  • 主 資深大佬 : kwklover

    @dongxiao
    @igeeky
    感谢，先保留，后续逐一研究学习。

  • 資深大佬 : yucongo

    bert （或其他 embedding ）＋ faiss 或许可以一试。其实好像也可以利用 elasticsearch

  • 資深大佬 : BiteTheDust

    从传统的字符串算法角度想了想
    对每个已有的文档建后缀自动机 然后用于查询的文档去对后缀自动机进行匹配 失配后回到原点重新继续匹配
    这样如果得到一些比较长的匹配结果就可以认为重复度比较高
    得到很多零碎的短匹配或者跟本匹配不上则可以认为重复度比较低
    时间复杂度的话与查询文档的大小 len 和已有文档的个数 n 相关 O(len*n)

  • 資深大佬 : FrankAdler

    布隆过滤器和 SimHash 以及完整 hash 是可以嵌套过滤的

  • 資深大佬 : ddup

    Lucene.NET 耗性能从大到小集中在几个地方：

    1.分词
    2.建立倒排索引
    3.搜索

    对于文档查重，可以在分词上做调整，是否有必要做细粒度的分词，比如是不是按句分词就够了（但是这样如果别人没有整句抄袭就无法检索到），那如果自定义一个粗粒度的分词器呢？

    加上由于分词粒度粗了，同样大小内容的检索时间也会降低，可以检索更多句子。

  • 資深大佬 : Lemeng

    我记得之前有个教程的，说是非常高效