V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
kwklover
V2EX  ›  程序员

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

  •  
  •   kwklover · 2021-02-16 23:42:55 +08:00 · 3035 次点击
    这是一个创建于 1136 天前的主题,其中的信息可能已经有所发展或是发生改变。
    因为最近做了个小项目,是一个站内查重系统(就是提交一个文档,判断这个文档与已有文档的重复率),因为预算不多,所以我想了个简单的实现方式:
    1,把待查重的文档的前 N 字(比如前 300 字),拆解为 10 个句子,分别去站内搜索,得出一个疑似重复度高的集合。
    2,把疑似集合的前 N 字与待分析文档,分别建立字表做准确分析,得出重复率百分比。

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

    各位 V 友大牛有没有更好的实现方式?
    28 条回复    2021-02-18 19:10:52 +08:00
    siyemiaokube
        1
    siyemiaokube  
       2021-02-17 03:42:17 +08:00 via iPhone
    随便 yy 了一下:
    词袋记录常见词,给站内文章打 tag,分别建索引

    然后把 input 随便剪一剪,分别词袋,根据 tag 对应的索引列表比对?
    sampeng
        2
    sampeng  
       2021-02-17 08:40:49 +08:00 via iPhone
    简单的向量相似性即可…
    sampeng
        3
    sampeng  
       2021-02-17 08:42:46 +08:00 via iPhone
    每个文档提交的时候酸一个向量值。查重就是比一下得事。应该飞快。比你查前 300 字,拆句,搜索快 n 倍。算法不超过 100 行代码
    xuanbg
        4
    xuanbg  
       2021-02-17 09:04:37 +08:00
    根据关键词的权重计算向量
    jeeyong
        5
    jeeyong  
       2021-02-17 09:20:05 +08:00
    jieba 分词, 把所有得词标号, 如果没有, 给一个新的.
    之后整篇文章获得一个类似[0, 25, 37, 178, 3578]得数组, 就是 2 楼说的向量了..
    后面不会了..谁来给我补补课..
    neoblackcap
        6
    neoblackcap  
       2021-02-17 09:46:09 +08:00 via iPhone
    snap 很多 bug,又不修。安装完系统第一件事就是卸装它
    DoctorCat
        7
    DoctorCat  
       2021-02-17 09:58:26 +08:00
    simhash
    laminux29
        8
    laminux29  
       2021-02-17 11:19:35 +08:00
    查重就没办法高效率,高效率的查重准确度不高。连谷歌处理这事都是砸钱去用空间换时间,没钱就只能消耗时间。
    noqwerty
        9
    noqwerty  
       2021-02-17 12:16:42 +08:00
    比较简单的办法是每个文档算 TF-IDF,然后用文档间的 cosine similarity 判断相似程度
    taowen
        10
    taowen  
       2021-02-17 15:08:29 +08:00
    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
        11
    kwklover  
    OP
       2021-02-17 16:00:14 +08:00
    @sampeng
    向量的比较真的有那么高效?一百万多数据,先得建立一百多万的向量,然后每个文档与一百多万的向量做比较,效率真的能飞快?

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


    @jeeyong
    分词的方式,依赖词库的分词方式,往往不太准确,结果就差别很大了,效果未必准确,小样本下测试偏差较大,大样本下没做测试,最后改为不分词,直接比较字。
    kwklover
        12
    kwklover  
    OP
       2021-02-17 16:04:56 +08:00
    @jeeyong
    我也不是专业 NLP,如果建立向量速度快,比较速度快,倒是可以研究一下。
    通过搜索的方式+字表比较的方式也能解决问题,就是建立 Lucene 索引的过程也是很吃资源,很耗费时间的,不过就是搜索快。
    ntest
        13
    ntest  
       2021-02-17 16:08:31 +08:00
    用 SimHash 比较吧,每个文档生成一次就行了
    kwklover
        14
    kwklover  
    OP
       2021-02-17 16:34:00 +08:00
    @ntest
    网上搜索了一下 SimHash 的资料,大概就是给每个文档建立一个 Hash,然后比较,所以比较的实现方式决定了最终的效率,不过 SimHash 可以计算出相似,但是具体相似多少,没法得出。
    dream4ever
        15
    dream4ever  
       2021-02-17 19:04:28 +08:00 via iPhone
    吴军当年在谷歌黑板报上就写了相关的文章,印象中是用矩阵运算之类的方法解决的,感兴趣可以搜搜。
    sampeng
        16
    sampeng  
       2021-02-17 20:33:35 +08:00 via iPhone
    @kwklover 又不是没次都是建 100 万次…每次入的时候计算一次这个新文档而已,就是第一次慢
    sampeng
        17
    sampeng  
       2021-02-17 20:36:18 +08:00 via iPhone
    另外 ps…要测试速度很简单…做一百万次除法就是每次查重需要的时间和 cpu 消耗
    jeeyong
        18
    jeeyong  
       2021-02-17 20:39:19 +08:00
    @kwklover 哈? 我一直默认你得需求属于小打小闹那种...哈哈哈...打扰了, 惹不起惹不起
    AX5N
        19
    AX5N  
       2021-02-17 21:10:11 +08:00
    这玩意是有算法的,建议去搜一下,不要自己想。
    kwklover
        20
    kwklover  
    OP
       2021-02-17 21:13:15 +08:00 via Android
    @jeeyong 不是默认,本来就是小打小闹的,欢迎大牛提供好的思路,目前的解决方案,解决百来万级的数据查重,勉强够用,再上一个量级,比如千万级数据量,那肯定慢死了,就是想征集一下不同的思路和方案。
    dongxiao
        21
    dongxiao  
       2021-02-17 21:57:25 +08:00 via Android
    试试 Embedding+FAISS
    igeeky
        22
    igeeky  
       2021-02-17 22:25:21 +08:00
    可以试试 postgresql. psql 支持文本相似度查询排序. 可以看看这个网页: https://developer.aliyun.com/article/59212
    kwklover
        23
    kwklover  
    OP
       2021-02-17 22:28:12 +08:00 via Android
    @dongxiao
    @igeeky
    感谢,先保留,后续逐一研究学习。
    yucongo
        24
    yucongo  
       2021-02-17 23:47:58 +08:00 via Android
    bert (或其他 embedding )+ faiss 或许可以一试。其实好像也可以利用 elasticsearch
    BiteTheDust
        25
    BiteTheDust  
       2021-02-18 00:14:45 +08:00
    从传统的字符串算法角度想了想
    对每个已有的文档建后缀自动机 然后用于查询的文档去对后缀自动机进行匹配 失配后回到原点重新继续匹配
    这样如果得到一些比较长的匹配结果就可以认为重复度比较高
    得到很多零碎的短匹配或者跟本匹配不上则可以认为重复度比较低
    时间复杂度的话与查询文档的大小 len 和已有文档的个数 n 相关 O(len*n)
    FrankAdler
        26
    FrankAdler  
       2021-02-18 04:24:21 +08:00
    布隆过滤器和 SimHash 以及完整 hash 是可以嵌套过滤的
    ddup
        27
    ddup  
       2021-02-18 12:24:15 +08:00
    Lucene.NET 耗性能从大到小集中在几个地方:

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

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


    加上由于分词粒度粗了,同样大小内容的检索时间也会降低,可以检索更多句子。
    Lemeng
        28
    Lemeng  
       2021-02-18 19:10:52 +08:00
    我记得之前有个教程的,说是非常高效
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2815 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 14:41 · PVG 22:41 · LAX 07:41 · JFK 10:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.