AC自动机

某个课程的作业,促使我来看看这玩意。

整个程序的算法思想是看别人的ACM的blog看懂的,感觉确实和KMP很像。但是代码呢就比较工程化一点。顺便回忆了一把ACM的感觉。

基本原理呢基于字典树,并增加了失败节点。

实现原理类似KMP算法,但是一次可以匹配多个字符串。在匹配失败时转向失败节点,并从失败节点开始继续向下匹配。

比如:我们有字典集合

acd、aceb、bef、cef

节点关系如图所示,红色为失败指针

digraph "ac_automation" {
    node [shape=box, fontsize = 14, labelfontsize = 14];
    edge [fontsize = 14, labelfontsize = 14];

    char_0 [label="0"];
    char_1 [label="1"];
    char_2 [label="2"];
    char_3 [label="acd"];
    char_4 [label="4"];
    char_5 [label="aceb"];
    char_6 [label="6"];
    char_7 [label="7"];
    char_8 [label="bef"];
    char_9 [label="9"];
    char_10 [label="10"];
    char_11 [label="cef"];

    char_0 -> char_1 [style=bold,label="a"];
    char_0 -> char_6 [style=bold,label="b"];
    char_0 -> char_9 [style=bold,label="c"];
    char_1 -> char_2 [style=bold,label="c"];
    char_2 -> char_9 [color=red];
    char_2 -> char_3 [style=bold,label="d"];
    char_2 -> char_4 [style=bold,label="e"];
    char_3 -> char_9 [color=red];
    char_4 -> char_10 [color=red];
    char_4 -> char_5 [style=bold,label="b"];
    char_5 -> char_10 [color=red];
    char_6 -> char_7 [style=bold,label="e"];
    char_7 -> char_8 [style=bold,label="f"];
    char_9 -> char_10 [style=bold,label="e"];
    char_10 -> char_11 [style=bold,label="f"];
}

当查找acefcab时,首先会按aceb的支路一直匹配到e,在e的位置发现找不到f,然后跳转到e的失败节点(即cef支路的e节点),查到f。并以此完成了第一次匹配。

接下来从根节点重新匹配并分别进入第一层的c节点,回到根节点,进入a节点,回到根节点,和进入b节点。

并在最终只匹配成功了cef

代码如下:

/**
 * AC 自动机, 数节点类和自动机功能类
 * 文档格式:doxygen
 * @author owentou, [email protected]
 * @date 2012.08.28
 */

#ifndef __AC_AUTOMATION_HPP_
#define __AC_AUTOMATION_HPP_

#if defined(_MSC_VER) && (_MSC_VER >= 1020)
# pragma once
#endif

#include <map>
#include <string>
#include <cstddef>
#include <list>
#include <vector>
#include <assert.h>
#include "smart_ptr.h"


template<typename CH = char>
class ACTrie: public std::enable_shared_from_this< ACTrie<CH> >
{
public:
    typedef std::shared_ptr< ACTrie<CH> > ptr_type;

private:
    /**
     * 关联的匹配字符串<br />
     * size不为0表示该节点有关联的字符串并且是最后一个节点
     */
    std::string m_strMatchedString;

    /**
     * 失败转向节点
     */
    ptr_type m_pFailed;

    /**
     * 下一个查找项
     */
    std::map<CH, ptr_type> m_stNext;

    /**
     * 初始化自身和子节点的失败指针
     * @param pPreFailed 初始搜索的指针(一般为父节点的失败指针)
     * @param cChar 搜索的字符
     */
    void _init_failed(ptr_type pPreFailed, const CH& cChar)
    {
        typedef typename std::map<CH, ptr_type>::iterator iter_type;

        // 设置自身的失败指针
        iter_type iter;
        for(;; pPreFailed = pPreFailed->m_pFailed)
        {
            iter = pPreFailed->m_stNext.find(cChar);
            if (iter != pPreFailed->m_stNext.end())
            {
                m_pFailed = iter->second;
                break;
            }

            if (NULL == pPreFailed->m_pFailed.get())
            {
                m_pFailed = pPreFailed;
                break;
            }
        }
    }

    /**
     * 把子节点填充到链表中(用于BFS)<br />
     * 调用此函数时,当前节点的失败指针必须已经设置好
     * @param stList 填充目标
     */
    void _fill_children(std::list< std::pair<CH, ptr_type> >& stList)
    {
        typedef typename std::map<CH, ptr_type>::iterator iter_type;
        for(iter_type iter = m_stNext.begin();
            iter != m_stNext.end();
            ++ iter)
        {
            iter->second->m_pFailed = m_pFailed;    // 临时用于记录父节点的失败指针
            stList.push_back(std::make_pair(iter->first, iter->second));
        }
    }

    /**
     * 获取当前指针
     * @return 当前对象的智能指针
     */
    ptr_type _get_ptr()
    {
        return this->shared_from_this();
    }
public:
    ACTrie(ptr_type pRoot): m_pFailed(pRoot){}

    /**
     * 设置失败指针
     * @param pFailed 失败指针
     */
    void SetFailed(ptr_type pFailed)
    {
        m_pFailed = pFailed;
    }

    /**
     * 初始化根节点中,子节点的失败指针<br />
     * 当前节点会被视为根节点
     */
    void InitFailed()
    {
        m_pFailed = ptr_type(NULL);
        std::list< std::pair<CH, ptr_type> > stList;

        typedef typename std::map<CH, ptr_type>::iterator iter_type;

        // 第一层节点
        for(iter_type iter = m_stNext.begin();
            iter != m_stNext.end();
            ++ iter)
        {
            iter->second->m_pFailed = _get_ptr();
            iter->second->_fill_children(stList);
        }

        // 后续节点 BFS 建树
        while (stList.size() > 0)
        {
            std::pair<CH, ptr_type> stNode = stList.front();
            stList.pop_front();
            stNode.second->_init_failed(stNode.second->m_pFailed, stNode.first);
            stNode.second->_fill_children(stList);
        }
    }

    /**
     * 清空后续分支
     */
    void Reset()
    {
        m_stNext.clear();
    }

    /**
     * 当前节点是否是一个关键字的最后一个节点
     * @return 如果是返回true
     */
    bool IsLastNode() const
    {
        return m_strMatchedString.size() > 0;
    }

    /**
     * 构建关键字的字典树节点
     * @param pStr          当前字符指针
     * @param iLeftBytes    关键字剩余字节数
     * @param strOrigin     关键字原始内容
     */
    void InsertChildren(const CH* pStr, int iLeftBytes, const std::string& strOrigin)
    {
        // 最后一个节点
        if (0 >= iLeftBytes)
        {
            m_strMatchedString.assign(strOrigin.data(), strOrigin.size());
            return;
        }

        iLeftBytes -= sizeof(CH);

        typedef typename std::map<CH, ptr_type>::iterator iter_type;
        iter_type iter = m_stNext.find(*pStr);
        if (iter != m_stNext.end())
        {
            iter->second->InsertChildren(pStr + 1, iLeftBytes, strOrigin);
            return;
        }

        std::pair<iter_type, bool> iter_new = m_stNext.insert(std::make_pair(*pStr, ptr_type(new ACTrie<CH>(m_pFailed))));
        assert(iter_new.second);

        iter_new.first->second->InsertChildren(pStr + 1, iLeftBytes, strOrigin);
    }

    /**
     * 匹配目标字符
     * @param pChar 目标字符指针
     * @param iLeftBytes 剩余字节数
     * @return 第一项为匹配完成后剩余字节数,第二项为匹配的关键字<br />
     *         如果匹配失败,第一项为0或负数,第二项为空串
     */
    std::pair<int, std::string> Match(const CH* pChar, int iLeftBytes) const
    {
        using namespace std;
        // 成功匹配
        if (IsLastNode())
        {
            return std::make_pair(iLeftBytes, m_strMatchedString);
        }

        // 已到目标串目末尾,无匹配
        if (iLeftBytes <= 0)
        {
            return std::make_pair(iLeftBytes, std::string(""));
        }

        // 匹配下一项
        typedef typename std::map<CH, ptr_type>::const_iterator iter_type;
        iter_type iter = m_stNext.find(*pChar);
        if (iter != m_stNext.end())
        {
            return iter->second->Match(pChar + 1, iLeftBytes - sizeof(CH));
        }
        // 如果是root节点,往后匹配
        if (NULL == m_pFailed->m_pFailed.get())
        {
            return Match(pChar + 1, iLeftBytes - sizeof(CH));
        }
        // 否则, failed节点进行匹配
        return m_pFailed->Match(pChar, iLeftBytes);
    }
};

template<typename CH = char>
class ACAutomation
{
public:
    typedef typename ACTrie<CH>::ptr_type trie_type;
    typedef std::pair<size_t, const std::string> item_type;
    typedef std::vector< item_type > value_type;

private:
    /**
     * 根节点(空节点)
     */
    std::shared_ptr< ACTrie<CH> > m_pRoot; 

    bool m_bIsInited;

    /**
     * 初始化字典树的失败指针
     */
    void init()
    {
        if (m_bIsInited)
            return;

        m_pRoot->InitFailed();

        m_bIsInited = true;
    }

public:
    ACAutomation():
        m_pRoot(new ACTrie<CH>( std::shared_ptr< ACTrie<CH> >(NULL) )),
        m_bIsInited(false)
    {
        // 临时的自环
        m_pRoot->SetFailed(m_pRoot);
    }

    ~ACAutomation()
    {
        // 解除自环,防止内存泄漏
        m_pRoot->SetFailed(std::shared_ptr< ACTrie<CH> >(NULL));
    }

    /**
     * 增加关键字
     * @param strKeyword 关键字字符串
     */
    void InsertKeyword(const std::string& strKeyword)
    {
        assert(strKeyword.size() > 0);

        m_bIsInited = false;
        m_pRoot->InsertChildren(static_cast<const CH*>(strKeyword.c_str()), strKeyword.size(), strKeyword);
    }

    /**
     * 匹配目标串,返回匹配结果
     * @param strContent 目标字符串
     * @return 返回的结果列表,返回结果的first为开始位置,second为匹配的关键字
     */
    value_type Match(const std::string& strContent)
    {
        using std::size_t;
        init();
        using namespace std;
        value_type ret;
        int iSize = static_cast<int>(strContent.size()), iLeft = iSize;
        const char* pEnd = strContent.data() + iSize;

        while (iLeft > 0)
        {
            pair<int, string> res = m_pRoot->Match(static_cast<const CH*>(pEnd - iLeft), iLeft);
            iLeft = res.first;
            if (res.second.size() > 0)
            {
                ret.push_back(std::make_pair(static_cast<size_t>(iSize - iLeft) - res.second.size(),
                    res.second));
            }
        }

        return ret;
    }

    /**
     * 清空关键字列表
     */
    void Reset()
    {
        m_pRoot->Reset();
    }
};

#endif

其中的 smart_ptr.h 文件见 https://www.owent.net/2012/643.html
注意:这段代码没经过边界条件测试、压力测试 等等各种测试,所以不是稳定版
接下来是测试使用的文件

/**
 * AC 自动机, 关键字过滤作业,匹配逻辑<br />
 * VC 11        中编译测试通过[Windows]
 * GCC 4.7.1    中编译测试通过[Linux]  (with -std=c++11 -lstdc++)
 * 文档格式:doxygen
 * @author owentou, [email protected]
 * @date 2012.08.25
 */

#include <iostream>
#include "ACAutomation.hpp"


int main()
{
    ACAutomation<> stAcTree;

    stAcTree.InsertKeyword("acd");
    stAcTree.InsertKeyword("aceb");
    stAcTree.InsertKeyword("bef");
    stAcTree.InsertKeyword("cef");

    ACAutomation<>::value_type stRes = stAcTree.Match("acefcab");

    for(auto stItem: stRes) 
    {
        std::cout<< "Position: "<< stItem.first<< " Matched Keyword: "<< stItem.second<< std::endl;
    }

    return 0;
}

如注释所言,4.7.0 以前的GCC 就不用争扎了,编译不过的

以下内容包含了完整对AC自动机的解释构建过程

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

2018-06-13 关于Java集合的小抄

15130
来自专栏Java3y

CopyOnWriteArrayList你都不知道,怎么拿offer?

前一阵子写过一篇COW(Copy On Write)文章,结果阅读量很低啊…COW奶牛!Copy On Write机制了解一下

12030
来自专栏函数式编程语言及工具

FunDA(12)- 示范:强类型数据源 - strong typed data sources

    FunDA设计的主要目的是解决FRM(Functional Relation Mapping)如Slick这样的批次型操作工具库数据源行间游动操作的缺失...

202100
来自专栏進无尽的文章

RunTime 之Method Swizzling

有关Runtime的知识总结,我本来想集中写成一篇文章的,但是最后发现实在是太长,而且不利于阅读,最后分成了如下几篇:

12320
来自专栏灯塔大数据

技术 | Python从零开始系列连载(十)

导读 Python特色数据类型(元组)(下) 元组和列表相互转化 ? ? 没错,只要在原来的列表外套一层tuple()就可以转为元组 在原来的元组外面套一层li...

34550
来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

18520
来自专栏CSDN技术头条

【问底】静行:FastJSON实现详解

还记得电影《功夫》中火云邪神的一句话:天下功夫,无坚不破,唯快不破。在程序员的世界中,“快”一直是大家苦苦修炼,竞相追逐的终极目标之一,甚至到了“不择手段”、“...

30870
来自专栏Pythonista

Python之路,Day2 - Python基础,列表,循环

11020
来自专栏Java技术栈

跟我学 Java 8 新特性之 Stream 流(二)关键知识点

我们的第一篇文章,主要是通过一个Demo,让大家体验了一下使用流API的那种酣畅淋漓的感觉。如果你没有实践,我还是再次呼吁你动手敲一敲,自己实实在跑一遍上一篇的...

14340
来自专栏Golang语言社区

用Golang写一个搜索引擎

本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

47670

扫码关注云+社区

领取腾讯云代金券