敏感词过滤技术之AC自动机

5 sec read

Aho-Corasick自动机算法(简称AC自动机)1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点,一个是扫描文本时完全不需要回溯,另一个是时间复杂度为O(n),时间复杂度与关键字的数目和长度无关。

而最原始的多模式匹配算法是O(mn)的时间复杂度。

AC算法思想:用多模式串建立一个确定性的树形有限状态机,以主串作为该有限状态机的输入,使状态机进行状态的转换,当到达某些特定的状态时,说明发生模式匹配。

下图是多模式he/she/his/hers构成的一个确定性有限状态机,做几点说明:

1、 该状态机优先按照实线标注的状态转换路径进行转换,当所有实线标注的状态转换路径条件不能满足时,按照虚线的状态转换路径进行状态转换。如:状态0时,当输入h,则转换到状态1;输入s,则转换到状态3;否则转换到状态0。

2、 匹配过程如下:从状态0开始进行状态转换,主串作为输入。如主串为:ushers,状态转换的过程是这样的:

3、  当状态转移到2,5,7,9等红色状态点时,说明发生了模式匹配。如主串为:ushers,则在状态5、2、9等状态时发生模式匹配,匹配的模式串有she、he、hers。

Python模块推荐:https://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

C语言学习:size_t

在学习C语言的时候,遇到了一个新的数据类型size_t,截止目前也没有完全理清这个类似的具体场景及出现的原因。
44 sec read

C语言学习:main()函数的正确写法

C语言虽然是一门古老的语言,但是其标准一直在完善,所以很多以前支持的语法在到当前已经不能在使用了。 C语言的版
41 sec read

Scipy数学函数的Scala实现

最近在推进项目的时候,遇到需要将线下的Python代码转化成线上的集群代码,由于机器代码环境是Scala,所以
4 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注