前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >敏感词检测算法小结

敏感词检测算法小结

作者头像
code4it
发布2018-09-17 14:51:30
5.4K0
发布2018-09-17 14:51:30
举报

本文简单介绍下敏感词或者脏词检测算法。

经典AC算法

经典的AC算法由三部分构成,goto表,fail表和output表,共包含四种具体的算法,分别是计算三张查找表的算法以及AC算法本身。

  • goto表是由模式集合P中的所有模式构成的状态转移自动机。(goto表就是一棵trie树)
  • failure表作用是在goto表中匹配失败后状态跳转的依据,这点与KMP中next表的作用相似。(这个表是trie树没有的,加了这个表,AC自动机就看起来不像一棵树,而像一个图)
  • output表示输出,又称:emits,即代表到达某个状态后某个模式串匹配成功 AC自动机本质上来说是一种基于trie树的kmp算法,AC算法需要三个函数来进行字符串匹配,而且这三个函数的求解都和一个确定的DFA(有限状态自动机)有关。

普通DFA算法

确定性有穷自动机,用于正则表达式的匹配,最长左子式匹配

使用hashmap

public void createKeyWord(String keyWord) {
        Map nowMap = sensitiveWordMap;
        for (Character c : keyWord.toCharArray()) {
            Object obj = nowMap.get(c);
            if (obj == null) {
                Map<String, Object> childMap = new HashMap<>();
                childMap.put("isEnd", "false");
                nowMap.put(c, childMap);
                nowMap = childMap;
            } else {
                nowMap = (Map) obj;
            }
        }
        nowMap.put("isEnd", "true");
    }

使用自定义数据结构

public class WordNode {
    private int value; // 节点名称
    private List<WordNode> subNodes; // 子节点
    private boolean isLast;// 默认false

    public WordNode(int value) {
        this.value = value;
    }
    public WordNode(int value, boolean isLast) {
        this.value = value;
        this.isLast = isLast;
    }
    //......
}

doc

  • 字符串多模式匹配:AC算法
  • Java实现DFA算法对敏感词、广告词过滤功能
  • 敏感词过滤的算法原理之 Aho-Corasick 算法
  • 敏感词过滤的算法原理之DFA算法
  • AC自动机和Fail树
  • 基于双数组的AC匹配算法学习
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2017-08-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码匠的流水账 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 经典AC算法
  • 普通DFA算法
    • 使用hashmap
      • 使用自定义数据结构
      • doc
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档