文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java DFA算法案例详解

2024-04-02 19:55

关注

1.背景

项目中需要对敏感词做一个过滤,首先有几个方案可以选择:

  1. 直接将敏感词组织成String后,利用indexOf方法来查询。
  2. 传统的敏感词入库后SQL查询。
  3. 利用Lucene建立分词索引来查询。
  4. 利用DFA算法来进行。

首先,项目收集到的敏感词有几千条,使用a方案肯定不行。其次,为了方便以后的扩展性尽量减少对数据库的依赖,所以放弃b方案。然后Lucene本身作为本地索引,敏感词增加后需要触发更新索引,并且这里本着轻量原则不想引入更多的库,所以放弃c方案。于是我们选定d方案为研究目标。

2.DFA算法简介

DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。其特征为:有一个有限状态集合和一些从一个状态通向另一个状态的边,每条边上标记有一个符号,其中一个状态是初态,某些状态是终态。但不同于不确定的有限自动机,DFA中不会有从同一状态出发的两条边标志有相同的符号。

简单点说就是,它是是通过event和当前的state得到下一个state,即event+state=nextstate。理解为系统中有多个节点,通过传递进入的event,来确定走哪个路由至另一个节点,而节点是有限的。

3.敏感词搜寻中的DFA算法

3.1敏感词库构造描述

以王八蛋和王八羔子两个敏感词来进行描述,首先构建敏感词库,该词库名称为SensitiveMap,这两个词的二叉树构造为:

 

用hash表构造为:

 

3.2基于敏感词库收索算法的描述

以上面例子构造出来的SensitiveMap为敏感词库进行示意,假设这里输入的关键字为:王八不好,流程图如下:

  

4.代码编写

4.1构造敏感词实现代码

4.2实现敏感词查询代码

5.优化思路

5.1敏感词中间填充无意义字符问题

对于“王*八&&蛋”这样的词,中间填充了无意义的字符来混淆,在我们做敏感词搜索时,同样应该做一个无意义词的过滤,当循环到这类无意义的字符时进行跳过,避免干扰。

5.2敏感词用拼音或部分用拼音代替

两种解决思路:一种是最简单是遇到这类问题,先丰富敏感词库进行快速解决。第二种是判断时将敏感词转换为拼音进行对比判断。

不过目前这两种方案均不能彻底很好的解决该问题,此类问题还需进一步研究。

到此这篇关于Java DFA算法案例详解的文章就介绍到这了,更多相关Java DFA算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯