精华内容
下载资源
问答
  • 经典的多模式串匹配算法AC的内存开销巨大,已经无法满足当前高速网络环境下大规模特征串实时匹配的应用需求。针对这一问题,提出一种空间高效的多模式串匹配算法—HashTrie。该算法运用递归散列函数,将模式串集合的...
  • 多模式串匹配概念多模式串匹配,即多个模式串在一个主串中进行匹配。虽然单模式串也能完成多模式串的匹配,但每个模式串都需要与主串进行匹配,如果遇到主串太长的情况,效率不高。而多模式串匹配,只需要扫描一次主...

    多模式串匹配概念

    多模式串匹配,即多个模式串在一个主串中进行匹配。

    虽然单模式串也能完成多模式串的匹配,但每个模式串都需要与主串进行匹配,如果遇到主串太长的情况,效率不高。

    而多模式串匹配,只需要扫描一次主串,大大提高效率。

    有一种经典的多模式串匹配算法 -- AC 自动机,全称是 Aho-Corasick 算法。下面来介绍其实现。

    AC 自动机

    AC 自动机在 Trie 树的基础上,增加了类似 KMP 的 next 数组,即每个节点会有个 fail 指针,指向某个节点。数据结构如下:

    class ACNode {

    var data: Character

    // 字符集 26 个小写字母

    var children: [ACNode?]

    var isEnd: Bool = false

    var fail: ACNode? = nil

    var len: Int = 0

    init(_ data: Character) {

    self.data = data

    children = [ACNode]()

    // 初始化 26 个

    var i = 0

    while i < 26 {

    children.append(nil)

    i += 1

    }

    }

    }

    准备工作

    将多个模式串构建成 Trie 树

    构建 fail 指针

    构建 Trie 树

    参考 Trie 树 的文章。

    构建 fail 指针

    fail 指针的生成类似于 KMP 中的next 数组计算方式,基于前一个值来计算。

    fail 指针的定义

    每个节点都有 fail 指针。假设节点为 p,当前串 str 为 root 到 p 的节点路径,找到其与所有模式串前缀匹配的最长后缀子串,那么 fail 就指向所匹配前缀的最后一个字符节点。

    后缀子串:不包括开头字符的子串。

    这里需要注意的是最长后缀子串,比如当前串为 abc,模式串为 bc、c。虽然其与 bc、c 都匹配,但最长的后缀子串是 bc。

    其中root.fail = NULL,若p是root的直接子节点,则p.fail = root。

    fail 指针的生成方法

    假设当前节点为 p,p.fail = q,pc 记为 p 的某个子节点,qc 记为 q 的某个子节点。

    若 pc == qc,则 pc.fail = qc。如下图所示:

    image.png

    若 pc != qc,则不断循环 q = q.fail,直到找到 q 的子节点与 pc 相等,或者 q == root结束。但如果 q == root,则说明没有后缀与模式串的前缀匹配,此时则令 pc.fail = root。再继续这两个过程。

    image.png

    按照树的广度遍历,逐个生成节点的 fail 指针。

    最终结果如下图所示:

    image.png

    Swift 代码如下:

    // 构建失败指针

    func buildFailPointer(_ root: ACNode) {

    var queue = Array()

    queue.append(root)

    while !queue.isEmpty {

    // 取出头部

    let p = queue.removeFirst()

    // 遍历其子节点

    if !p.children.isEmpty {

    for pc in p.children {

    if let pc = pc {

    // 如果父节点是 root,则 fail 指针直接指向 root

    if p === root {

    pc.fail = root

    } else {

    var q = p.fail

    while q != nil {

    // 如果 pc 在 q 的子节点 qc 中存在,则直接指向 qc

    let index = indexOfChar(pc.data)

    if (index >= 0 && index <= q!.children.count) {

    if let qc = q!.children[index] {

    pc.fail = qc

    } else {

    // 不存在,找 q 的 fail 指针

    q = q!.fail

    }

    }

    }

    // 不存在,则指向 root

    if q == nil {

    pc.fail = root

    }

    }

    queue.append(pc)

    }

    }

    }

    }

    }

    模式串匹配

    首先需要明确以下两点:

    若p 的节点路径 A ( root 到 p 的路径)匹配主串,则 p.fail 的节点路径 B 也是匹配的。因为 A 的后缀子串与B 的前缀是相同的,所以前面肯定匹配,同理 p.fail.fail 的节点路径也是。

    因此只需要不断遍历其 fail 指针节点,判断是否为结束符,如果是,则该模式串就是匹配主串的。

    在某条分支路径上 A 做匹配,如果遇上不匹配的情况,则切到其 fail 指针指向的另外一条分支 B ,再继续匹配。因为其前后缀相同。

    具体算法

    逐个遍历主串的字符,判断该字符是否存在当前节点 p 的子节点中。

    如果存在,则 p 指向其子节点,然后循环遍历 p 链式的 fail 指针指向的节点是否为模式串的结尾,若是,该模式串匹配完成。

    如果不存在,则循环遍历 fail 的链式指针进行查找,若没找到,则节点 p 重新指回 root。重复这 2 个步骤。

    Swift 代码如下:

    // 进行匹配

    func match(_ text: String, _ root: ACNode) {

    // 逐个遍历主串

    var p: ACNode? = root

    var i = 0

    while i < text.count {

    let strIndex = text.index(text.startIndex, offsetBy: i)

    let ch = text[strIndex]

    // 判断 p 的子节点是否匹配 ch,如果不匹配,则往 fail 指针找

    let index = indexOfChar(ch)

    while p?.children[index] == nil && p !== root {

    p = p?.fail

    }

    p = p?.children[index]

    // 一直没有匹配,重新指回 root

    if p == nil {

    p = root

    }

    // 遍历其 fail 指针,找到结束的字符,即为匹配

    var tmp = p

    while tmp != nil {

    if tmp!.isEnd {

    print("match startPosition:\(i - tmp!.len + 1)")

    }

    tmp = tmp?.fail

    }

    i += 1

    }

    }

    展开全文
  • AC自动机实现多模式串匹配,支持中文系统,同时可以支持多个模式串,测试使用Linux和Windows系统,使用20条模式串,中英文混合,测试通过
  • 多模式串匹配之AC自动机算法
  • * HashTrie一种空间高效的多模式串匹配算法 张萍,刘燕兵,于静,谭建龙 1 中国科学院 信息工程研究所北京 100093 2 中国科学院大学北京 100049 3 信息内容安全技术国家工程实验室北京 100093 HashTrie算法在随机数据集...
  • AC自动机:如何用多模式串匹配实现敏感词过滤功能? 用字符串匹配算法,通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词,如果有,就用***...

    AC自动机:如何用多模式串匹配实现敏感词过滤功能?

    用字符串匹配算法,通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词,如果有,就用***替代

    如何实现一个高性能的敏感词过滤系统?多模式串匹配算法

    基于单模式串和Trie树实现的敏感词过滤

    BF 、RK、BM、KMP、Trie树中,前四个是单模式串匹配算法,只有Trie树是多模式串匹配算法

    所谓的单模式串就是一个模式串和一个主串之间匹配,多模式串就是多个模式串和一个主串之间做匹配

    如何用Trie树实现敏感词过滤功能呢?

    对敏感词进行预处理,构建Trie树结构,如果敏感词字符动态更新了,只需要动态更新一下Trie树即可,当用户输入一个文本内容后,把用户输入的内容作为主串,从第一个字符开始,在Trie树中匹配,当匹配到Trie树的叶子节点时候或遇到不匹配的字符时候,将主串的开始匹配位置往后移动一位,就是从起始字符的下一个字符开始重新在Trie树中匹配

    更高效的经典多模式串匹配算法:AC自动机

    Trie和AC自动机之间的关系就像单串匹配中朴素的串匹配算法,跟KMP算法一样,只不过Trie树针对的是多模式串而已,所以AC自动机就是在Trie树之上,加了类似KMP的next数组,只不过现在的next数组是构建在树上罢了

    public class AcNode{
    	public char data;
    	public AcNode[] children = new AcNode[26];//字节集只包含a~z这26个字符
    	public boolean isEndingChar = false; //结尾字符为true
    	public int length = -1;   //当isEndingChar = true时,记录模式串长度
    	public AcNode fail;//失败指针
    	public AcNode(char data){
    		this.data = data;
    	}
    }
    

    AC自动机的构建包含两个操作:

    • 将多个模式串构建成Trie树
    • 在Trie树上构建失败指针(相当于KMP中的失效函数next数组)

    构建好Trie树后如何在它之上构建失败指针?

    比如有4个模式串 c , bc , bcd , abcd,主串是abcd

    ​ root

    ​ a b c

    ​ b c

    c d

    ​ d

    Trie树中的每一个节点都有一个失败指针,假如沿Trie树走到p节点,就是红色节点 c,那p的失败指针就是从root走到红色节点形成的字符串abc,跟所有模式串前缀匹配的最长可匹配后缀子串,就是箭头指的bc模式串

    关于最长可匹配后缀子串,字符串abc的后缀子串有两个bc,c,拿它们与其他模式串匹配,如果某个后缀子串可以匹配某个模式串的前缀,把这个后缀子串叫做可匹配后缀子串,从可匹配后缀子串中找出最长的一个,就是最长可匹配后缀子串

    将p节点的失败指针指向那个最长可匹配后缀子串对应的模式串的前缀的最后一个节点,就是从第一个c指向的第二个c

    失败指针的构建过程是一个按层遍历树的过程,如果root的失败指针为null,就是指向自己

    当我们已经求个某个节点p的失败指针之后,如何寻找它的子节点的失败指针?

    设节点p的失败指针指向节点q,看节点p的子节点pc对应的字符是否可以在节点q的子节点中找到,如果找到了节点q的一个子节点qc,对应的字符跟节点pc对应的字符相同,将节点pc的失败指针指向节点qc,如果节点q中没有子节点的字符等于节点pc包含的字符,令q = q ->fail(fail表示失败指针),继续查找,直到q= root为止,如果没有找到相同字符的子节点,就让节点pc的失败指针指向root

    构建失败指针:
    public void buildFailurePointer(){
    	Quene<AcNode> quene = new LinkedList<>();
    	root.fail = null;
    	quene.add(root);
    	while(!quene.isEmpty()){
    		AcNode p = quene.remove();
    		for(int i = 0 ; i < 26 ; ++i){
    			AcNode pc = p.children[i];
    			if(pc == null) continue;
    			if(p == root){
    			pc.fail = root;
    			}else{
    				AcNode q = p.fail;
    				while(q != null){
    					AcNode qc = q.children[pc.data - 'a'];
    					if(qc != null){
    						pc.fail = qc;
    						break;
    					}
    					q = q.fail;
    				}
    				if(q == null){
    					pc.fail = root;
    				}
    			}
    			quene.add(pc);
    		}
    	}
    }
    
    如何在AC自动机上匹配主串?

    过程中,主串从i = 0开始,AC自动机从指针 p = root开始,假设模式串是b,主串是a

    • 如果p指向的节点有一个等于b[i]的子节点x,更新p指向x,这时候需要通过失败指针,检测一系列失败指针为结尾的路径是否是模式串,处理后,i+1,继续
    • 如果p指向的节点没有=b[i]的子节点,让p = p->fail

    匹配的代码:(代码输出的是在主串中每个可以匹配的模式串出现的位置)

    public void match(char[] text){     //text是主串
    	int n = text.length;
    	AcNode p = root;
    	for(int i = 0 ; i < n ; ++i){
    		int idx = text[i] - 'a';
    		while(p.children[idx] == null && p != root){
    			p = p.fail;        //失败指针发挥作用的地方
    		}
    		p = p.children[idx];
    		if(p == null)  p = root;   //如果没有匹配的,从root开始重新匹配
    		AcNode tmp = p ;
    		while (tmp != root){  //打印出可以匹配的模式串
    			if(tmp.isEndingChar == true){
    				int pos = i - tmp.length+1;
    				System.out.println("匹配起始下标" + pos + ";长度" + tmp.length);
    			}
    			tmp = tmp.fail;
    		}
    	}
    }
    

    AC自动机实现的敏感词过滤系统,是否比单模式串匹配方法更高效?

    将敏感词构建成AC自动机,包括构建Trie树以及失败指针

    从复杂度上看,AC自动机匹配的效率跟Trie树一样,实际上失效指针大部分指向root,

    https://www.cnblogs.com/sclbgw7/p/9260756.html

    https://www.cnblogs.com/hyfhaha/p/10802604.html

    展开全文
  • 多模式串匹配 多模式串匹配的场景常见于一些平台屏蔽某些用户的发言中的敏感词条。 用字符串匹配算法找出文本中的敏感词条,并用“***”代替。虽然可以使用单模式串匹配算法逐个进行查找敏感词条,再进行替换,...

    多模式串匹配

    多模式串匹配的场景常见于一些平台屏蔽某些用户的发言中的敏感词条。

    用字符串匹配算法找出文本中的敏感词条,并用“***”代替。虽然可以使用单模式串匹配算法逐个进行查找敏感词条,再进行替换,但是实际场景中,若敏感词的库很大,并且要匹配的文本内容很多,则匹配时长过长,很可能导致发一条消息发好久。显然这会导致用户体验下降。

    因此,需要一种在多个模式串下的高效匹配算法来应对这种场景。

    基于 Trie 树过滤敏感词

    Trie 树本身就是基于多模式串匹配的算法,将多个模式串构建成一棵 Trie 树,当模式串有变动时,只需要改变 Trie 树就可以了。

    与主串匹配时,从主串的第一个字符开始逐个与 Trie 树进行匹配,当匹配到坏字符时,我们将主串的开始字符往后移一个,继续从 Trie 树根开始匹配,这样一来我们只需要扫描一遍主串就可以完成对多个模式串的匹配工作。效率远远高于用单模式串匹配。

    AC 自动机原理

    上述基于 Trie 树的多模式串匹配算法类似于单模式串匹配中的暴力匹配算法,我们知道暴力匹配算法可以通过引入 next 数组来提高效率,即 KMP 算法,那么在这个多模式串匹配中,能否将 next 数组这样的思想加入其中呢?

    答案显然是肯定的,只需要将 Trie 树稍微改造一下即可,当然不是加 next 数组,而是在 Trie 树每个节点中加入一个next指针,即失败指针

    如图,字符c的失败指针是字符串bcf中的c,当我们匹配到abc后,发现与字符d不匹配了,此时可以通过c的失败指针跳转到bcd中,接着去匹配f
    失败指针
    如此一来,便不再是遇到匹配不上重头开始匹配了,思想与 next 数组一样,如果没理解 KMP 算法的原理,建议先弄明白 next 数组,再看这个失败指针就很容易理解了(KMP 算法推荐阅读:著名字符串匹配算法:KMP 算法原理分析和代码实现

    接下来的问题是,如何才能找到每个节点的失败指针指向的下一个节点呢?
    Trie 树实际上就是包括了所有模式串的,假设我们现在要求上图中的节点c的失败指针,已知条件是匹配到c处时,abc是已经与主串匹配成功的前缀,接着需要匹配的模式串应该是abc的后缀子串为前缀子串的其他模式串,并且是最长可匹配的前缀子串

    abc的后缀子串有cbc,其他模式串中只有bcf的前缀bcabc的后缀子串可匹配,因此c的失败指针应该指向bcfc

    构建自动机

    构建一个自动机的条件如下:

    1. 构建一棵 Trie 树
    2. 初始化节点失败指针

    首先来看一下每个节点的数据结构:

    public class AcNode {
        public char data; //数据域
        public AcNode[] children = new AcNode[26]; //字符集只包含a~z这26个字符
        public boolean isEndingChar = false; //记录模式串结尾字符
        public int length = -1; //记录模式串长度
        public AcNode fail; // 失败指针
        public AcNode(char data) {
          this.data = data;
        }
    }
    

    可以发现,与 Trie 树相比只是多了一个失败指针

    因此构建自动机的第一步是构建一棵 Trie 树,这部分内容此处不再细讲(参见 Trie 树构造原理、应用场景与复杂度分析)。

    现在我们要考虑的问题是,构建完 Trie 树后,如何才能得到所有节点的失败指针?

    通过上面的分析,我们已经知道要得到某个节点的失败指针指向的节点,其实就是要找与这个节点所在的前部分模式串的后缀子串匹配的最长前缀子串

    在一棵 Trie 树中,某个节点的失败指针指向的节点只会在它的上层。因此,可以采用求 next 数组一样的方法,求失败指针,即通过已经求得失败指针的节点来推导当前节点的失败指针。

    根节点root的失败指针是 null,即指向自己,然后,求得某个节点p的失败指针q后,如何去求它子节点的失败指针?

    情况一:将p的子节点与q的子节点互相比较,若相同,则找到对应的失败指针了。
    在这里插入图片描述
    情况二:若p的子节点与q的子节点存在不相等的,那么我们通过q的失败指针,获得对应节点,继续查找子节点,直到查到 null 为止,即 root 节点。
    在这里插入图片描述

    下面是构建失败指针的代码:

    public void buildFailurePointer(AcNode root) {
        Queue<AcNode> queue = new LinkedList<>();
        root.fail = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            AcNode p = queue.remove();//拿到节点p
            for (AcNode pc : p.children) {//遍历节点p的子节点
                if (pc == null) continue;
                if (p == root) {//root的子节点失败指针为root
                    pc.fail = root;
                } else {
                    AcNode q = p.fail;//找到p的失败指针节点q
                    while (q != null) {
                    	//查找p的子节点是否存在q的子节点
                        AcNode qc = q.children[pc.data - 'a'];
                        if (qc != null) {//存在则找到失败指针
                            pc.fail = qc;
                            break;
                        }
                        q = q.fail;//否则继续找下一个失败指针
                    }
                    if (q == null) {//直到找到null,则失败指针为root
                        pc.fail = root;
                    }
                }
                queue.add(pc);
            }
        }
    }
    

    构建完失败指针后,如图:
    在这里插入图片描述

    使用 AC 自动机匹配

    假设主串str,从主串第一个字符开始匹配,自动机从指针p=root开始匹配

    1. 假设p的子节点x等于str[0],则把p更新为x,接着要检查p(当前指向x)的失败指针是否是某个模式串的结尾,若是,则查找到一个匹配的模式串。处理完之后,继续匹配str[2]。
    2. 若进行到某一步后,p的子节点中没有找到能匹配的字符,那么,失败指针就派上用场了,即:在失败指针指向的节点的子节点中查找。
    public void match(char[] str, AcNode root) { // str是主串,root是自动机
        AcNode p = root;
        for (int i = 0; i < str.length; i++) {
            int idx = str[i] - 'a';
            //p的子节点中没有,就往p的失败节点的子节点中找,直到失败指针指向null为止
            while (p.children[idx] == null && p != root) {
                p = p.fail; // 失败指针发挥作用的地方
            }
            p = p.children[idx];//找到匹配的字符后,p更新指向到这个节点
            if (p == null)// 如果没有匹配的,从 root 开始重新匹配
                p = root; 
            AcNode tmp = p;
            while (tmp != root) { // 找到已经匹配到的模式串
                if (tmp.isEndingChar == true) {
                    int pos = i - tmp.length + 1;
                    System.out.println(" 匹配起始下标 " + pos + "; 长度 " + tmp.length);
                }
                tmp = tmp.fail;
            }
        }
    }
    

    AC 自动机匹配的效率

    1. Trie 树构建的复杂度是O(m*len),其中m为模式串数量,len为模式串平均长度。
    2. 构建失败指针时,最耗时的是 while 循环中逐层往上查找失败指针,每次循环至少往上一层,而树的高度不超过len,因此时间复杂度为O(K*len),K 为 Trie 树中的节点个数。
    3. 以上两步操作只需执行一次完成构建,不影响与主串匹配的效率,在匹配时,最耗时的同样是 while 循环中往下一个失败指针的代码,因此时间复杂度为O(len),若主串长度为n,那么总匹配时间复杂度为O(n*len)

    实际在匹配敏感词时,敏感词的平均长度不会很长,因此,AC 自动机的匹配效率很接近O(n),只有在极端情况下,效率才会退化成与 Trie 树匹配效率一样。

    极端情况如下:
    极端的AC自动机

    展开全文
  • 基于存储压缩的多模式串匹配算法,一种多模式匹配机的很好的改进。
  • BF、RK、BM、KMP 算法都是针对只有一个模式串的字符串匹配算法,而要实现一个高性能的敏感词过滤系统,就需要用到多模式匹配算法了。 1. 基于单模式和 Trie 树实现的敏感词过滤 多模式匹配算...

    网站上的敏感词过滤是怎么实现的呢?

    实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容后,通过字符串匹配算法来检查用户输入的内容是否包含敏感词。

    BF、RK、BM、KMP 算法都是针对只有一个模式串的字符串匹配算法,而要实现一个高性能的敏感词过滤系统,就需要用到多模式匹配算法了。

    1. 基于单模式和 Trie 树实现的敏感词过滤

    多模式匹配算法,就是在多个模式串和一个主串之间做匹配,也就是在一个主串中查找多个模式串。

    敏感词过滤,也可以通过单模式匹配算法来实现,那就是针对每个敏感值都做一遍单模式匹配。但如果敏感词很多,并且主串很长,那我们就需要遍历很多次主串,显然这种方法是非常低效的。

    而多模式匹配算法只需要扫描一遍主串,就可以一次性查找多个模式串是否存在,匹配效率就大大提高了。那如何基于 Trie 树实现敏感词过滤功能呢?

    我们可以首先对敏感词字典进行预处理,构建成 Trie 树。这个预处理的操作只需要做一次,如果敏感词字典动态更新了,我们只需要在 Trie 树中添加或删除一个字符串即可。

    用户输入一个文本内容后,我们把用户输入的内容作为主串,从第一个字符开始在 Trie 树中进行匹配。当匹配到叶子节点或者中途遇到不匹配字符的时候,我们就将主串的匹配位置后移一位,重新进行匹配。

    基于 Trie 树的这种处理方法,有点类似单模式匹配的 BF 算法。我们知道 KMP 算法在 BF 算法基础上进行了改进,每次匹配失败时,尽可能地将模式串往后多滑动几位。同样,在这里,我们是否也可以对多模式串 Trie 树进行同样的改进呢?这就要用到 AC 自动机算法了。

    2. AC 自动机多模式匹配算法

    AC 自动机算法,全称是 Aho-Corasick 算法。AC 自动机实际上就是在 Trie 树之上,加了类似于 KMP 算法的 next 数组,只不过此处的数组是构建在树上罢了

    class ACNode
    {
    public:
    
        char data;
        bool is_ending_char;   // 是否结束字符
        int length;            // 当前节点为结束字符时记录模式串长度
        ACNode *fail;          // 失败指针
        ACNode *children[26];  // 字符集只包含 a-z 这 26 个字符
    
        ACNode(char ch)
        {
            data = ch;
            is_ending_char = false;
            length = -1;
            fail = NULL;
            for (int i = 0; i < 26; i++)
                children[i] = NULL;
        }
    };
    复制代码

    AC 自动机的构建包含两个操作:

    • 将多个模式串构建成 Trie 树;

    • 在 Trie 树上构建失败指针,就相当于 KMP 算法中的失效函数 next 数组。

    构建 Trie 树的过程可以参考 Trie 树——搜索关键词提示,这里只是多了一个模式串的长度而已。假设我们的 4 个模式串分别为 c,bc,bcd,abcd,那么构建好的 Trie 树如下所示。

    Trie 树中的每一个节点都有一个失败指针,它的作用和构建过程,和 KMP 算法中 next 数组极其相似。

    假设我们沿着 Trie 树走到 p 节点,也就是下图中的紫色节点,那 p 的失败指针也就是从根节点走到当前节点所形成的字符串 abc,和所有模式串前缀匹配的最长可匹配后缀子串,这里就是 bc 模式串。

    字符串 abc 的后缀子串有 c 和 bc,我们拿它们和其它模式串进行匹配,如果能够匹配上,那这个后缀就叫作可匹配后缀子串。在一个字符串的所有可匹配后缀子串中,长度最长的那个叫作最长可匹配后缀子串。我们就将一个节点的失败指针指向其最长可匹配后缀子串对应的模式串前缀的最后一个节点。

    其实,如果我们把树中相同深度的节点放到同一层,那么某个节点的失败指针只有可能出现在它所在层的上面。因此,我们可以像 KMP 算法那样,利用已经求得的、深度更小的那些节点的失败指针来推导出下面节点的失败指针。

    首先,根节点的失败指针指向 NULL,第一层节点的失败指针都指向根节点。然后,继续往下遍历,如果 p 节点的失败指针指向 q,那么我们需要看节点 p 的子节点 pc 对应的字符,是否也可以在节点 q 的子节点 qc 中找到。如果找到了一个子节点 qc 和 pc 的字符相同,则将 pc 的失败指针指向 qc。

    如果找不到一个子节点 qc 和 pc 的字符相同,那么我们继续令 q = q->fail,重复上面的查找过程,直到 q 为根节点为止。如果还没有找到,那就将 pc 的失败指针指向根节点。

    // 构建失败指针
        void build_failure_pointer()
        {
            queue<ACNode *> AC_queue;
            AC_queue.push(root);
    
            while (!AC_queue.empty())
            {
                ACNode *p = AC_queue.front();
                AC_queue.pop();
                for (int i = 0; i < 26; i++)
                {
                    ACNode *pc = p->children[i];
    
                    if (pc == NULL) continue;
                    if (p == root) pc->fail = root;
                    else
                    {
                        ACNode *q = p->fail;
                        while (q != NULL)
                        {
                            ACNode *qc = q->children[pc->data - 'a'];
                            if (qc != NULL)
                            {
                                pc->fail = qc;
                                break;
                            }
                            q = q->fail;
                        }
    
                        if (q == NULL) pc->fail = root;
                    }
                    AC_queue.push(pc);
                }
            }
        }
    复制代码

    通过按层来计算每个节点的子节点的失败指针,例中最后构建完之后的 AC 自动机就是下面这个样子。

    接下来,我们看如何在 AC 自动机上匹配子串?首先,主串从 i=0 开始,AC 自动机从指针 p=root 开始,假设模式串是 b,主串是 a。

    • 如果 p 指向的节点有一个等于 a[i] 的子节点 x,我们就更新 p 指向 x,这时候我们还要检查这个子节点的一系列失败指针对应的路径是否为一个完整的模式串,之后我们将 i 增 1,继续重复这两个过程;

    • 如果 p 指向的节点没有等于 a[i] 的子节点,我们就更新 p = p->fial,继续重复这两个过程。

        // 在 AC 自动机中匹配字符串
        void match_string(const char str[])
        {
            ACNode *p = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                while (p->children[index] == NULL && p != root)
                {
                    p = p->fail;
                }
                p = p->children[index];
    
                if (p == NULL) p = root; // 没有可匹配的,从根节点开始重新匹配
                ACNode *temp = p;
                while (temp != root)
                {
                    if (temp->is_ending_char == true)
                    {
                        int pos = i - temp->length + 1;
                        cout << "Fing a match which begins at position " << pos << ' '
                        << "and has a length of " << temp->length << '!'<< endl;
                    }
                    temp = temp->fail;
                }
            }
        }
    复制代码

    全部代码如下:

    #include <iostream>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    class ACNode
    {
    public:
    
        char data;
        bool is_ending_char;   // 是否结束字符
        int length;            // 当前节点为结束字符时记录模式串长度
        ACNode *fail;          // 失败指针
        ACNode *children[26];  // 字符集只包含 a-z 这 26 个字符
    
        ACNode(char ch)
        {
            data = ch;
            is_ending_char = false;
            length = -1;
            fail = NULL;
            for (int i = 0; i < 26; i++)
                children[i] = NULL;
        }
    };
    
    class AC
    {
    private:
    
        ACNode *root;
    
    public:
    
        // 构造函数,根节点存储无意义字符 '/'
        AC()
        {
            root = new ACNode('/');
        }
    
        // 向 Trie 树中添加一个字符串
        void insert_string(const char str[])
        {
            ACNode *cur = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                if (cur->children[index] == NULL)
                {
                    ACNode *temp = new ACNode(str[i]);
                    cur->children[index] = temp;
                }
                cur = cur->children[index];
            }
            cur->is_ending_char = true;
            cur->length = strlen(str);
        }
    
        // 构建失败指针
        void build_failure_pointer()
        {
            queue<ACNode *> AC_queue;
            AC_queue.push(root);
    
            while (!AC_queue.empty())
            {
                ACNode *p = AC_queue.front();
                AC_queue.pop();
                for (int i = 0; i < 26; i++)
                {
                    ACNode *pc = p->children[i];
    
                    if (pc == NULL) continue;
                    if (p == root) pc->fail = root;
                    else
                    {
                        ACNode *q = p->fail;
                        while (q != NULL)
                        {
                            ACNode *qc = q->children[pc->data - 'a'];
                            if (qc != NULL)
                            {
                                pc->fail = qc;
                                break;
                            }
                            q = q->fail;
                        }
    
                        if (q == NULL) pc->fail = root;
                    }
                    AC_queue.push(pc);
                }
            }
        }
    
        // 在 AC 自动机中匹配字符串
        void match_string(const char str[])
        {
            ACNode *p = root;
            for (unsigned int i = 0; i < strlen(str); i++)
            {
                int index = int(str[i] - 'a');
                while (p->children[index] == NULL && p != root)
                {
                    p = p->fail;
                }
                p = p->children[index];
    
                if (p == NULL) p = root; // 没有可匹配的,从根节点开始重新匹配
                ACNode *temp = p;
                while (temp != root)
                {
                    if (temp->is_ending_char == true)
                    {
                        int pos = i - temp->length + 1;
                        cout << "Fing a match which begins at position " << pos << ' '
                        << "and has a length of " << temp->length << '!'<< endl;
                    }
                    temp = temp->fail;
                }
            }
        }
    };
    
    int main()
    {
        //char str[][8] = {"how", "he", "her", "hello", "so", "see", "however"};
        char str[][5] = {"abce", "bcd", "ce"};
    
        AC test;
        for (int i = 0; i < 7; i++)
        {
            test.insert_string(str[i]);
        }
    
        test.build_failure_pointer();
        //test.match_string("however, what about her boyfriend?");
        test.match_string("abcfabce");
    
        return 0;
    }
    复制代码

    3. AC 自动机的复杂度分析

    首先,构建 Trie 树的时间复杂度为 O(m*len),其中 len 表示敏感词的平均长度,m 表示敏感词的个数。

    其次,假设 Trie 树中总共有 k 个节点,每个节点在构建失败指针的时候,最耗时的就是 while 循环部分,这里 q = q->fail,每次节点的深度都在减小,树的最大深度为 len,因此每个节点构建失败指针的时间复杂度为 O(len),整个失败指针构建过程的时间复杂度为 O(k*len)。不过,AC 自动机的构建过程都是预先处理好的,构建好之后并不会频繁更新。

    最后,假设主串的长度为 n,匹配的时候每一个 for 循环里面的时间复杂度也为 O(len),总的匹配时间复杂度就为 O(n*len)。因为敏感词不会很长,而且这个时间复杂度只是一个非常宽泛的上限,实际情况下,可能近似于 O(n),所以,AC 自动机匹配的效率非常高。

    从时间复杂度上看,AC 自动机匹配的效率和 Trie 树一样,但是一般情况下,大部分节点的失败指针都指向根节点,AC 自动机实际匹配的效率要远高于 O(n*len)。只有在极端情况下,AC 自动机的性能才会退化为和 Trie 树一样。

    参考资料-极客时间专栏《数据结构与算法之美》

    获取更多精彩,请关注「seniusen」!

    展开全文
  • 改进(加上前后缀)后Wu—Manber多模式串匹配算法,很经典、Java实现很难得,本人已应用于某短彩信平台系统产品中进行关键词检测,性能很优!
  • 多模式串匹配问题(设m为目标串的长度,n为模式串的平均长度)。可以用后缀trie树,时间复杂度为O(m^2 + kn)。利用AC自动机的时间复杂度为O(m + kn + z)(其中z为T中出现的模式串个数)。还可以用后缀树,后缀树的...
  • 标准KMP算法用于单一模式串匹配,即在母串中寻求一个模式串匹配,但是现在又存在这样的一个问题,如果同时给出模式串,要求找到这一系列模式串在母串存在的匹配个数,我们应该如何处理呢?基于KMP算法,我们...
  • 文章目录基于单模式串和 Trie 树实现的敏感词过滤经典的多模式串匹配算法:AC 自动机解答开篇内容小结 很多支持用户发表文本内容的网站,比如 BBS,大都会有敏感词过滤功能,用来过滤掉用户输入的一些淫秽、反动、...
  • 数据结构与算法之美 - 36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?基于单模式串和 Trie 树实现的敏感词过滤经典的多模式串匹配算法:AC 自动机解答开篇内容小结 很多支持用户发表文本内容的网站,比如 ...
  • 标准KMP算法用于单一模式串匹配,即在母串中寻求一个模式串匹配,但是现在又存在这样的一个问题,如果同时给出模式串,要求找到这一系列模式串在母串存在的匹配个数,我们应该如何处理呢? 基于KMP算法,...
  • AC自动机就是字典树+KMP,解决了一个在字典树中的匹配问题。
  • 网站上的敏感词过滤是怎么...BF、RK、BM、KMP 算法都是针对只有一个模式串的字符串匹配算法,而要实现一个高性能的敏感词过滤系统,就需要用到多模式匹配算法了。 1. 基于单模式和 Trie 树实现的敏感词过滤 多模...
  • ------ 本文是学习算法的笔记,《数据...实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含...
  • 实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词。如果有,就用“***”把它替代掉...
  • 多模式串匹配算法扫描一次主串实现匹配,这样的效率就很高了。我们可以对敏感词做预处理,构建一棵Trie树。用户输入内容后,把用户输入的内容作为主串,从第一个字符C开始匹配。当匹配 到Trie树的叶子节点或者中途有...
  • 程序说明:多模式串匹配的AC自动机算法 自动机算法可以参考《柔性字符串匹配》里的相应章节,讲的很清楚 */ #include #include const int MAXQ = 500000+10; const int MAXN = 1000000+10; const int MAXK = 26;...
  • AC算法:多模式串匹配、前缀匹配 而AC算法是KMP算法向多模式串情景的扩展,因此当部分匹配某模式串时,查找的是:既是该 部分匹配模式串部分的 后缀 ,同时又是 需匹配模式串集合中某个模式串的 前缀 的 最长 ...
  • 给一个二维字符数组和w个模式串,求这w个模式串在二维字符数组的位置。 分析: 静态trie树。 代码: //poj 1204 //sep9 #include using namespace std; const int maxN=1024; const int maxM=270*maxN; char str...
  • 支持用户发表文本内容的网站,比如 BBS,大都会有敏感词过滤...实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找...
  • AC自动机算法全称Aho-Corasick算法,是一种字符串多模式匹配算法。该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。AC算法用于在一段文本中查找多个模式字符,即给你很多字符,再给你一段文本,让你...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,429
精华内容 2,971
关键字:

多模式串匹配