V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member  Sign In
aidevs
V2EX  ›  问与答

非法关键词过滤系统该怎么做?有没有更好的思路?

  •  
  •   aidevs · Aug 26, 2016 · 3593 views
    This topic created in 3533 days ago, the information mentioned may be changed or developed.
    非法关键词日积月累会越来越多
    不可能写个 for 循环,遍历所有关键词,然后再查找“内容”中有没有这个关键词吧?效率低
    当然我知道一些东西 Spark 可以分布式计算 还不太会用,只是了解了功能可能会用上
    但是有没有更好的算法呢?

    我目前想到的一些主要思路:

    [需求]
    需要过滤的 “内容” 和 “非法关键字”

    第一步
    非法关键字把首字进行 md5 取第一位 如:
    SB 这个词 每个字符 md5 只拿 md5 中的 第一位 如:
    SB
    13

    第二步
    把内容中的每个字符 md5 只拿 md5 中的 第一位 如:
    每个字符进行 md5 并且取 md5 的第一位
    你是 SB 就注定无泪无悔
    a 1 13 4 5 3 3 b x c
    然后每个字符都有一个 0-9a-f 对应

    把得到的字符 组合为下列方式,存储为一个数组:
    a1
    11
    13
    34
    45
    53
    33
    3b
    bx
    xc


    第三步
    把非法关键字分散到 256 个字典中
    00
    01
    02
    ..
    ff


    第四步
    for 循环 第二步得到的数组,去查询非法关键字的 256 个字典
    得到 可能的所有非法关键字

    第五步

    详细对比 content.IndexOf(第四步中得到的词)
    11 replies    2016-08-27 20:38:47 +08:00
    ShadowStar
        1
    ShadowStar  
       Aug 26, 2016   ❤️ 1
    bloom-filter
    scnace
        2
    scnace  
       Aug 26, 2016 via Android
    bloom filter +1
    holyghost
        3
    holyghost  
       Aug 26, 2016
    DAT
    nobodyhere
        4
    nobodyhere  
       Aug 26, 2016
    内容长度为 n ,关键词个数为 m ,这个单次过滤的复杂度为 O(n*m),做离线过滤还可以勉强凑合,放线上应对 QPS 就惨了
    标准做法是做出 O(n*1),用 trie 树
    UnisandK
        5
    UnisandK  
       Aug 26, 2016
    对内容中每个字符取 md5 会爽到飞起吧
    SourceMan
        6
    SourceMan  
       Aug 26, 2016
    https://github.com/imaben/php-akm 只有个 PHP 版的,可以参考实现
    shakoon
        7
    shakoon  
       Aug 26, 2016
    每个字符都去算 md5 ……我觉得这不会比每个关键字都去 like 一遍节约资源
    NeinChn
        8
    NeinChn  
       Aug 26, 2016
    有 TRIE 还是用 TRIE 吧,比 BloomFilter 靠谱
    mayokaze
        9
    mayokaze  
       Aug 26, 2016
    ac 自动机
    aidevs
        10
    aidevs  
    OP
       Aug 27, 2016
    @ShadowStar
    @NeinChn
    @scnace
    @holyghost
    这么多人推荐 BloomFilter ,有空去试试 DAT 是什么?
    holyghost
        11
    holyghost  
       Aug 27, 2016 via iPhone
    @dbfox double array trie
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   5440 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 62ms · UTC 01:29 · PVG 09:29 · LAX 18:29 · JFK 21:29
    ♥ Do have faith in what you're doing.