PHP版的AC多模式匹配算法

时间:2014-12-05 08:19:20
【文件属性】:

文件名称:PHP版的AC多模式匹配算法

文件大小:23KB

文件格式:RAR

更新时间:2014-12-05 08:19:20

多模式 AC AhoCorasick 匹配 算法

AC多模式匹配算法 特点:应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点:一是扫描文本时完全不需要回溯,二是时间复杂度为O(n)与关键字的数目和长度无关,但所需时间和文本长度以及所有关键字的总长度成正比。 算法思想:用多模式串建立一个确定性的树形有限状态机,以主串作为该有限状态机的输入,使状态机进行状态的转换,当到达某些特定的状态时,说明发生模式匹配。AC 多模式匹配算法的实现可分预处理和搜索查找两个阶段。在预处理阶段根据待匹配的模式串组生成有限状态机;搜索查找阶段状态机根据输入的文本串进行状态跳转,当到达某一状态时,该状态有匹配的模式串,则匹配成功。AC 状态机包括goto、fail 和output 3 个函数。 实现步骤:1. 构造字典树;2. 搜索路径的确定(即构造失败指针);3. 模式匹配过程。


【文件预览】:
ac.php
----php.ac.demo.rar(16KB)
----php.ac.src.rar(6KB)

网友评论

  • 很好的资源,推荐
  • 能提供思路
  • 测试了下,很正确。看了相关的算法,很难懂,IQ不够用啊
  • 资源不错,非常有用,在简单数据分析场景下非常实用
  • 挺有用的 谢谢
  • 测试了下,很正确。看了相关的算法,很难懂,IQ不够用啊
  • 已经在生产环境使用,很不错
  • 下来看了,速度慢了点
  • 效果不错,可以用
  • 慢的要死,还不如正则了,写这玩意干吗