• 概述
    • 由来
      • 思路
    • DFA介绍

    概述

    由来

    在我最早入职的一家公司,主要负责内容方面的业务,对我来说大部分的工作是对内容的清洗和规整。当然,清洗过程免不了的就是按照关键词过滤,你懂的。需求如下:

    后台人员添加N个关键字,然后对主站所有的内容进行清洗,含有这些关键字的所有内容都置为无效。

    思路

    拿到此需求,我最早的方案比较粗暴:针对关键字建立一个HashSet,然后遍历整个数据库,针对每篇文章遍历这个Set,查找是否contains关键字……好吧我承认这不是一个好方法,随着关键字的增多和数据的增多,这个过程消耗的时间成指数型增长!

    于是我找到度娘,发现一个算法:DFA。

    DFA介绍

    DFA全称为:Deterministic Finite Automaton,即确定有穷自动机。因为本人算法学的不好,有兴趣的可以看这篇博客: 基于DFA敏感词查询的算法简析

    解释起来原理其实也不难,就是用所有关键字构造一棵树,然后用正文遍历这棵树,遍历到叶子节点即表示文章中存在这个关键字。

    我们暂且忽略构建关键词树的时间,每次查找正文只需要O(n)复杂度就可以搞定。

    针对DFA算法以及网上的一些实现,Hutool做了整理和改进,最终形成现在的Hutool-dfa模块。