精华内容
下载资源
问答
  • ok { return false } p = p.Children[index] } if p.IsEndingChar == false { return false } return true } func main(){ strs := [...]string{"Laravel", "Framework", "PHP"} trie := &GoTrie{} ...
    package main
    
    import "fmt"
    
    type TrieNode struct {
    	Date string
    	Children map[string]*TrieNode
    	IsEndingChar bool
    }
    
    type GoTrie struct {
    	Root *TrieNode
    }
    
    func (this *GoTrie) Insert(text string) {
    
    	p := this.Root
    
    	for i:=0; i < len(text); i++ {
    		index := string(text[i])
    		data := index
    		if p.Children == nil {
    			p.Children = make(map[string]*TrieNode)
    		}
    		if _, ok := p.Children[index]; !ok {
    			newNode := &TrieNode{
    				Date:data,
    			}
    			p.Children[index] = newNode
    		}
    
    		p = p.Children[index]
    	}
    
    	p.IsEndingChar = true
    }
    
    func (this *GoTrie) Find(pattern string) bool {
    	p := this.Root
    
    	for i:=0; i<len(pattern); i++ {
    		index := string(pattern[i])
    
    		if _, ok := p.Children[index]; !ok {
    			return false
    		}
    
    		p = p.Children[index]
    	}
    
    	if p.IsEndingChar == false {
    		return false
    	}
    	return true
    }
    
    func main(){
    	strs := [...]string{"Laravel", "Framework", "PHP"}
    	trie := &GoTrie{}
    	trie.Root = &TrieNode{}
    
    	for _, str := range strs {
    		trie.Insert(str)
    	}
    
    	fmt.Println(trie.Root.Children["F"].Children)
    
    	fmt.Println(trie.Find("PHP"))
    	fmt.Println(trie.Find("PHPA"))
    }
    
    
    展开全文
  • 字符串匹配算法Trie树)

    千次阅读 多人点赞 2019-06-25 01:25:37
    是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串。 Trie树本质,利用字符串之间的公共前缀,将重复的前缀合并在一起。 2. Trie树操作 2.1 存储 Trie树是一个多叉树;二叉树的...

    1. Trie树概念

    • Trie树,也叫字典树,它是一个树形结构。是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串。
    • Trie树本质,利用字符串之间的公共前缀,将重复的前缀合并在一起。
      在这里插入图片描述

    2. Trie树操作

    2.1 存储

    Trie树是一个多叉树;二叉树的数据结构里存放着左右子节点的指针;
    Trie树采用的一种经典的存储方式是散列表
    在这里插入图片描述

    class TrieNode//Trie树节点类,假设只有26个字母的数据集
    {
    public:
        char data;
        TrieNode *children[charNum];
        size_t count;//记录这个节点被多少个单词占用
        bool isEndOfWord;//是否是一个单词的结束字符
        size_t freq;    //单词插入的频次
        TrieNode(char ch = '/'):data(ch), isEndOfWord(false), count(0), freq(0)
        {
            memset(children,0,sizeof(TrieNode*) * charNum);
        }
        ~TrieNode(){}
    };
    

    Trie树比较浪费内存,children数组存放指针;
    牺牲点效率的话,可以将数组改成,有序数组,跳表,散列表,红黑树等

    2.2 查找

    TrieNode* find_private(const string &text) const//查找某个字符串,返回最后一个字符节点的指针
    {
        TrieNode *p = root;
        int index;
        for(int i = 0; i < text.size(); ++i)
        {
            index = text[i] - 'a';
            if(p->children[index] == NULL)
                return NULL;//还没匹配完
            p = p->children[index];
        }
        if(p->isEndOfWord == false)//匹配完,但是只是前缀
            return NULL;
        else
        {
            return p;//私有find无输出信息
        }
    }
    

    时间复杂度O(k),k为要查找的字符串长度

    2.3 插入

    void insert(const string &text)//插入一个字符串
    {
        TrieNode *p = find_private(text);
        if(p)//找到了字符串,不用插入,频次加1
        {
            p->freq++;
            return;
        }
        p = root;
        int index;
        for(int i = 0; i < text.size(); ++i)
        {
            index = text[i] - 'a';
            if(p->children[index] == NULL)
            {
                TrieNode *newNode = new TrieNode(text[i]);
                p->children[index] = newNode;
            }
            p->count++;
            p = p->children[index];
        }
        p->count++;
        p->freq++;
        p->isEndOfWord = true;
    }
    

    时间复杂度O(n),n为所有字符串长度和

    2.4 删除

    bool delString(const string &text)
    {
        TrieNode *p = root;
        stack<TrieNode*> nodeStack;
        nodeStack.push(root);
        int index;
        for(int i = 0; i < text.size(); ++i)
        {
            index = text[i] - 'a';
            if(p->children[index] == NULL)
                return false;//还没匹配完
            p = p->children[index];
            nodeStack.push(p);
        }
        if(p->isEndOfWord == false)//匹配完,但是只是前缀
            return false;
        else
        {
            while(nodeStack.top()->count == 1)//删除单词只要自己包含的部分
            {
                index = nodeStack.top()->data - 'a';
    //            cout << "del char: " << nodeStack.top()->data << endl;//(调试代码)
                delete nodeStack.top();
                nodeStack.pop();
            }
            nodeStack.top()->children[index] = NULL;//断开已删除的部分
            while(!nodeStack.empty())
            {
                nodeStack.top()->count--;//单词占用记录减1
                nodeStack.pop();
            }
            return true;
        }
    }
    

    析构函数

    void destory(TrieNode* proot)//树不再使用,结束前,释放资源
    {
        if(proot == NULL)
        {
            return;
        }
        for(int i = 0; i < charNum; ++i)
        {
            destory(proot->children[i]);
        }
        delete proot;
        proot = NULL;
    }
    

    2.5 打印

    	void printStrWithPre(const string prefix) const//打印有指定前缀的单词
        {
            if(prefix.size() == 0)
                return;
            TrieNode *p = root;
            int index,printID = 0;
            for(int i = 0; i < prefix.size(); ++i)
            {
                index = prefix[i] - 'a';
                if(p->children[index] == NULL)//前缀还没匹配成功
                {
                    cout << "-------------------------" << endl;
                    cout << "no string with prefix: " << prefix << " can be found!" << endl;
                    return;
                }
                else
                    p = p->children[index];
            }//匹配完了,p指向前缀最后一个字符节点
            cout << "-------------------------" << endl;
            cout << p->count << " string(s) with prefix: " << prefix << " , as following:" << endl;
            printWordsOfNode(p,prefix,printID);
            cout << "-----------end-----------" << endl;
        }
        void printDict() const//字典序输出全部单词
        {
            string word("");
            int printID = 0;
            cout << "-------------------------" << endl;
            cout << "all " << itemCount() << " words as following:" << endl;
            printWordsOfNode(root,word,printID);
            cout << "-----------end-----------" << endl;
        }
    private:
        void printWordsOfNode(TrieNode* p, string prefix, int &order) const
        {//递归打印前缀最后一个字符对应节点下面所有的字符
            if(p != NULL)
            {
                if(p->isEndOfWord)//是终止字符,prefix是不断+出来的,是整个字符串
                    cout << ++order << " " << prefix << ", frequency: " << p->freq << endl;
                for(int i = 0; i < charNum; ++i)
                {
                    if(p->children[i] != NULL)
                        printWordsOfNode(p->children[i],prefix+(p->children[i]->data),order);
                }
            }
        }
    

    3. 完整代码

    https://github.com/hitskyer/course/blob/master/dataAlgorithm/chenmingming/string_matching/trie.cpp

    /**
     * @description: trie树,字典树
     * @author: michael ming
     * @date: 2019/6/24 19:00
     * @modified by: 
     */
    #include <iostream>
    #include <cstring>
    #include <stack>
    #define charNum 26
    using namespace std;
    class TrieNode//Trie树节点类,假设只有26个字母的数据集
    {
    public:
        char data;
        TrieNode *children[charNum];
        size_t count;//记录这个节点被多少个单词占用
        bool isEndOfWord;//是否是一个单词的结束字符
        size_t freq;    //单词插入的频次
        TrieNode(char ch = '/'):data(ch), isEndOfWord(false), count(0), freq(0)
        {
            memset(children,0,sizeof(TrieNode*) * charNum);
        }
        ~TrieNode(){}
    };
    class Trie
    {
    public:
        TrieNode* root;
        Trie()
        {
            root = new TrieNode;
        }
        ~Trie()
        {
            destory(root);
        }
        void insert(const string &text)//插入一个字符串
        {
            TrieNode *p = find_private(text);
            if(p)//找到了字符串,不用插入,频次加1
            {
                p->freq++;
                return;
            }
            p = root;
            int index;
            for(int i = 0; i < text.size(); ++i)
            {
                index = text[i] - 'a';
                if(p->children[index] == NULL)
                {
                    TrieNode *newNode = new TrieNode(text[i]);
                    p->children[index] = newNode;
                }
                p->count++;
                p = p->children[index];
            }
            p->count++;
            p->freq++;
            p->isEndOfWord = true;
        }
        void find(const string &text) const//查找某个字符串
        {
            TrieNode *p = root;
            int index;
            for(int i = 0; i < text.size(); ++i)
            {
                index = text[i] - 'a';
                if(p->children[index] == NULL)//还没匹配完
                {
                    cout << "can not find string: " << text << endl;
                    return;
                }
                p = p->children[index];
            }
            if(p->isEndOfWord == false)//匹配完,但是只是前缀
            {
                cout << "can not find string: " << text << endl;
                return;
            }
            else
            {
                cout << text << " occurs " << p->freq << " time(s)." << endl;
                return;
            }
        }
    
    private:
        TrieNode* find_private(const string &text) const//查找某个字符串,返回最后一个字符节点的指针
        {
            TrieNode *p = root;
            int index;
            for(int i = 0; i < text.size(); ++i)
            {
                index = text[i] - 'a';
                if(p->children[index] == NULL)
                    return NULL;//还没匹配完
                p = p->children[index];
            }
            if(p->isEndOfWord == false)//匹配完,但是只是前缀
                return NULL;
            else
            {
                return p;//私有find无输出信息
            }
        }
    
    public:
        void destory(TrieNode* proot)//树不再使用,结束前,释放资源
        {
            if(proot == NULL)
            {
                return;
            }
            for(int i = 0; i < charNum; ++i)
            {
                destory(proot->children[i]);
            }
            delete proot;
            proot = NULL;
        }
        bool delString(const string &text)
        {
            TrieNode *p = root;
            stack<TrieNode*> nodeStack;
            nodeStack.push(root);
            int index;
            for(int i = 0; i < text.size(); ++i)
            {
                index = text[i] - 'a';
                if(p->children[index] == NULL)
                    return false;//还没匹配完
                p = p->children[index];
                nodeStack.push(p);
            }
            if(p->isEndOfWord == false)//匹配完,但是只是前缀
                return false;
            else
            {
                while(nodeStack.top()->count == 1)//删除单词只要自己包含的部分
                {
                    index = nodeStack.top()->data - 'a';
    //                cout << "del char: " << nodeStack.top()->data << endl;//(调试代码)
                    delete nodeStack.top();
                    nodeStack.pop();
                }
                nodeStack.top()->children[index] = NULL;//断开已删除的部分
                while(!nodeStack.empty())
                {
                    nodeStack.top()->count--;//单词占用记录减1
                    nodeStack.pop();
                }
                return true;
            }
        }
        size_t itemCount() const//字典中单词种数
        {
            return root->count;
        }
        void printStrWithPre(const string prefix) const//打印有指定前缀的单词
        {
            if(prefix.size() == 0)
                return;
            TrieNode *p = root;
            int index,printID = 0;
            for(int i = 0; i < prefix.size(); ++i)
            {
                index = prefix[i] - 'a';
                if(p->children[index] == NULL)//前缀还没匹配成功
                {
                    cout << "-------------------------" << endl;
                    cout << "no string with prefix: " << prefix << " can be found!" << endl;
                    return;
                }
                else
                    p = p->children[index];
            }//匹配完了,p指向前缀最后一个字符节点
            cout << "-------------------------" << endl;
            cout << p->count << " string(s) with prefix: " << prefix << " , as following:" << endl;
            printWordsOfNode(p,prefix,printID);
            cout << "-----------end-----------" << endl;
        }
        void printDict() const//字典序输出全部单词
        {
            string word("");
            int printID = 0;
            cout << "-------------------------" << endl;
            cout << "all " << itemCount() << " words as following:" << endl;
            printWordsOfNode(root,word,printID);
            cout << "-----------end-----------" << endl;
        }
    private:
        void printWordsOfNode(TrieNode* p, string prefix, int &order) const
        {//递归打印前缀最后一个字符对应节点下面所有的字符
            if(p != NULL)
            {
                if(p->isEndOfWord)//是终止字符,prefix是不断+出来的,是整个字符串
                    cout << ++order << " " << prefix << ", frequency: " << p->freq << endl;
                for(int i = 0; i < charNum; ++i)
                {
                    if(p->children[i] != NULL)
                        printWordsOfNode(p->children[i],prefix+(p->children[i]->data),order);
                }
            }
        }
    };
    int main()
    {
        Trie textlib;
        string a("hello"), b("her"), c("so"), d("hi"), e("how"), f("see");
        textlib.insert(a);
        textlib.insert(a);
        textlib.insert(b);
        textlib.insert(c);
        textlib.insert(d);
        textlib.insert(e);
        textlib.insert(f);
        textlib.find(a);
        textlib.find(b);
        textlib.find(d);
        textlib.printStrWithPre("h");
        textlib.printDict();
        textlib.delString("hello");
        textlib.find(a);
        textlib.printStrWithPre("h");
        textlib.printDict();
        cout << "total kind(s) of word: " << textlib.itemCount() << endl;
        return 0;
    }
    

    在这里插入图片描述

    4. Trie树与散列表、红黑树的比较

    Trie树对要处理的字符串有及其严苛的要求。

    • 第一,字符串中包含的字符集不能太大。如果字符集太大,那存储空间可能就会浪费很多。即便可以优化,也要付出牺牲查询、插入效率的代价。
    • 第二,要求字符串的前缀重合比较多,不然空间消耗会变大很多。
    • 第三,如果要用Trie树解决问题,那我们就要自己从零开始实现一个Trie树,还要保证没有bug,这个在工程上是将简单问题复杂化,除非必须,一般不建议这样做。
    • 第四,通过指针串起来的数据块是不连续的,而Trie树中用到了指针,所以,对缓存并不友好,性能上会打个折扣。
    • 综合这几点,针对在一组字符串中查找字符串的问题,工程中更倾向于用散列表或者红黑树。因为这两种数据结构,我们都不需要自己去实现,直接利用编程语言中提供的现成类库就行了。
    • Trie 树只是不适合精确匹配查找,这种问题更适合用散列表或者红黑树来解决。
    • Trie树比较适合的是查找前缀匹配的字符串,例如搜索引擎智能匹配输入,给出候选提示(如果有多个候选,可以按搜索热度排序,上面代码里面的 frequency)。
      在这里插入图片描述
    • Trie树还可以应用于自动输入补全(输入法,代码编辑器,浏览器网址输入)

    4.1 思考题

    • 上面针对英文的搜索关键词,对于更加复杂的中文来说,词库中的数据又该如何构建成Trie 树呢?
    • 如果词库中有很多关键词,在搜索提示的时候,用户输入关键词,作为前缀在Trie 树中可以匹配的关键词也有很多,如何选择展示哪些内容呢?(按搜索热度或者概率)
    • 像Google 这样的搜索引擎,用户单词拼写错误的情况下,Google还是可以使用正确的拼写来做关键词提示,这个又是怎么做到的呢?

    参考文章

    https://www.cnblogs.com/xujian2014/p/5614724.html

    5. 练习题

    LeetCode 1707. 与数组中元素的最大异或值(Trie树)

    展开全文
  • 允许模糊字符串匹配Trie 数据结构 这是 Steve Hanov 在他的编写的 Python 程序的 Go 版本 这已经完成了,但没有测试。 ###这个怎么运作 这是一个基本的 。 您可以搜索作为字符串后缀的所有单词。 您还可以...
  • 1. 他是一种树形结构,是一种专门处理字符串匹配的数据结构,解决在一组字符串集合中快速查找某个字符串的问题。 2. Trie树的本质是利用字符串之间公共前缀,将重复的前缀合并在一起 Trie 树的本质,就是利用字符串...
    1. 单模式串匹配
      BF 算法和 RK 算法
      BM 算法和 KMP 算法
    2. 多模式串匹配算法
      Trie 树和 AC 自动机

    一、 什么是“Trie树”?

    1. 他是一种树形结构,是一种专门处理字符串匹配的数据结构,解决在一组字符串集合中快速查找某个字符串的问题。

    2. Trie树的本质是利用字符串之间公共前缀,将重复的前缀合并在一起

    Trie 树的本质,就是利用字符串之间的公共前缀,将重复的前缀合并在一起。

    how,hi,her,hello,so,see
    在这里插入图片描述

    其中,根节点不包含任何信息,每个节点表示一个字符串中的字符,从根节点到红色节点的一条路径表示一个字符串(红色节点并不都是叶子节点)。

    3. 查找

    当在Trie树中查找一个字符串时,如“her”,就将要查找的字符串分割成单个的字符h,e,r,然后从Trie树的根节点开始匹配。但,假若要查找的字符串是“he”,用上面同样的方法,从根节点开始,沿着某条路径来匹配,发现路径的最后一个节点“e”不是红色的,即“he”是某个字符串的前缀,但不能完全匹配任何字符串。

    二 、如何实现一课Trie树?

    1,Trie树主要有两个操作,一个是将字符串集合构造成Trie树。这个程可分解为:

    • 将一个字符串插入到Trie树的过程
    • 在Trie树中查询一个字符串

    2,如何存储一个Trie树

    ①:Trie树是一个多叉树,需要存储一个节点的所有子节点的指针。
    ②:一种经典的存储方式:借助散列表额思想,通过一个下标与字符一一映射的数组,来存储子节点的指针。

    class TrieNode {
      char data;
      TrieNode children[26];
    }
    

    借助散列表的思想,我们通过一个下标与字符一一映射的数组,来存储子节点的指针。
    在这里插入图片描述
    假设字符串中只有从a到z这26个小写字母,从数组中下标为0的位置,存储指向子节点a的指针,下标为1的位置存储指向子节点b的指针,以此类推,下标为25的位置,储存的是指向的子节点z的指针。如果某个字符的子节点不存在,就在对应的下标的位置存储null。
    当在Trie树中查找字符串的时候,就可以通过字符的ASCII码减去“a”的ASCII码,迅速找到匹配的子节点的指针。

    
    public class Trie {
      private TrieNode root = new TrieNode('/'); // 存储无意义字符
    
      // 往Trie树中插入一个字符串
      public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; ++i) {
          int index = text[i] - 'a';
          if (p.children[index] == null) {
            TrieNode newNode = new TrieNode(text[i]);
            p.children[index] = newNode;
          }
          p = p.children[index];
        }
        p.isEndingChar = true;
      }
    
      // 在Trie树中查找一个字符串
      public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) {
          int index = pattern[i] - 'a';
          if (p.children[index] == null) {
            return false; // 不存在pattern
          }
          p = p.children[index];
        }
        if (p.isEndingChar == false) return false; // 不能完全匹配,只是前缀
        else return true; // 找到pattern
      }
    
      public class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;
        public TrieNode(char data) {
          this.data = data;
        }
      }
    }
    

    3,时间复杂度:

    构建 Trie 树 时间复杂度 O(n)(n 表示所有字符串的长度和)
    在 Trie 树中,查找某个字符串的时间复杂度 O(k),k 表示要查找的字符串的长度
    在一组字符串中,频繁的查询某些字符串,用Trie树非常高效。

    4,Trie树很耗内存吗?

    Trie树是使用数组来储存一个节点的子节点的指针的,即便一节点只有很少的子节点,远小于26个,比如2,3个,也要维护一个长度为26的数组。
    Trie的本质是避免重复存储一组字符串的相同前缀子串,但现在每个字符(对应一个节点)的存储远远大于1个字节。
    如果字符串中不仅包含小写字母,还包含大写字母,数字,甚至是中文,那需要的存储空间就更多了。所以在重复前缀并不多的情况下,Trie树不但不节省内存,还有可能浪费更多的内存。

    5,Tri树的优化方案:
    • 牺牲一点查询的效率,将每个节点中的数组换成其他数据结构,来存储一个节点指针。如:有序数组,跳表,散列表,红黑树等。
      假设用有序数组,数组中的指针按照指向的子节点中的字符大小顺序排序。查询时,可以通过二分查找的方法,快速查找到某个字符应该匹配的子节点的指针。

    • 缩点优化,就是对只有一个子节点的节点,而且此节点不是一个串的结束节点,可以将此子节点合并。这样可以节省空间,但却增加了编码难度。

    三 、Trie数与散列表的,红黑树的比较(应用与局限 )

    1,字符串的匹配问题,笼统上讲,其实就是数据的查找问题。

    2,在一组字符串中查找字符串,Trie数实际上表现的并不好,他对要处理的字符串有极其严苛的要求:

    • 第一,字符中包含的字符集不能太大,如果字符集太大,那么存储空间就可能浪费很多。即便优化也要付出牺牲查询,插入效率的代价。
    • 第二,要求字符串的前缀重合比较到,不然空间消耗会变大很多。
    • 第三,如果要用Trie树解决问题,就需要自己从零开始实现一个Trie树,还要保证没有bug,这在工程上是把简单问题复杂化。
    • 第四,通过指针串起来的数据是不连续的,而Trie树用到了指针,所以,对缓存并不友好。性能上会打个折扣。

    综上:Trie树不适合精确匹配查找,这种问题更适合用散列表或红黑树来解决。Trie树比较适合的是查找前缀匹配的字符串。Trie的这个特点可以扩展到更加广泛的一个应用上:自动输入补全。比如输入法自动补全功能、IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。

    笔记整理来源: 王争 数据结构与算法之美

    展开全文
  • 基于Trie树的高效敏感词过滤算法,interesting! 和单模式的KMP算法相似。

    1. 算法背景

    之前介绍过单模式串匹配的高效算法:BM和KMP 以及 基于多模式串的匹配数据结构Trie树。

    1. BM和KMP 单模式串匹配算法细节

    2. Trie树 多模式串的高效匹配数据结构

    当有这样的需求:对于输入的主串,需要替换其中的敏感词为其他字符,也就是需要对trie树中的字符串逐个匹配,来判断该字符串是否在主串中,从而将其替换为制定字符。比如输出主串:abacdab , 使用Trie树构建的字符集如下:abc, ac,dab,最终替换的主串为: aba***** 。

    如果用Trie树的匹配方式:

    会拿着每一个trie树中的字符串 来和主串匹配,如果主串中没有这个字符串,则匹配trie树中的下一个字符串。
    在这里插入图片描述

    以root的26个字符为外层循环进行遍历,如果root->children_[des[i]-‘a’]不为空,则循环当前的trie树中的字符,且主串的i++,直到Trie树的叶子结点,发现当前trie树的这个字符串没法匹配,则从trie树的root重新开始匹配下一个trie树中的字符串。

    基本的代码如下:

    其中的AcNode也就是Trie-tree 中的TrieNode,下文的代码其实已经完成了Trie树的构建,相关的代码可以在开头的Trie树实现中查看。

    // Match trie str with traditional method.
    void matchLow(string des) {
      vector<pair<int,int>> match_vec;
      AcNode *tmp = root_;
      int des_len = des.size();
      int i = 0;
    
      // Traverse the des string which is user's input
      while(i < des_len) {
        int index = des[i] - 'a';
        AcNode *p = tmp->children_[index];
    		// Match every single str in trie tree
        while(p != nullptr) {
          i ++;
          p = p->children_[des[i]-'a'];
        }
    
        if (p->isEndingChar_ == true) {
          int pos = i - p->length_ + 1;
          match_vec.push_back(make_pair(pos, p->length_));
          cout << "pos: " << pos << " len :" 
            << tmp -> length_ << endl;
        } else {
          i++;
        }
      }
    }
    

    也就是每一个Trie树中的字符串都需要在主串中匹配一遍,这样的效率其实是比较低的。

    有没有办法让在Trie树中的遍历跳过的字符更多一些呢?就像单模式串中KMP算法一样,让模式串在主串中的每一次移动尽可能多的位置,来降低匹配次数。kmp通过一个失效函数来达到这样的目的,同理Trie中也可以用一种算法,让主串尽可能多得匹配trie 树中的模式字符串,降低模式字符串的匹配次数,这个思想也就是AC自动机的算法思想,了解这个算法思想之前需要非常熟悉Trie树以及KMP算法的原理,文章开头有链接。

    2. AC自动机实现原理

    AC自动机全称Aho-Corasick 算法,实际原理就是在Trie树之上构建类似KMP的next数组,这里则是在Trie树上构建而已。

    AcNode数据结构如下:

    class AcNode {
    public:
      char data_; // AcNode char
      bool isEndingChar_; // Ending pos
      int length_; // Length of the string
      AcNode *children_[26]; 
      AcNode *fail; // fail pointer, to construct
                    // the next array on Trie-tree
    
      AcNode(char data='/') 
      :data_(data),isEndingChar_(false), length_(0){
        memset(children_, 0, sizeof(AcNode *)* 26);
      };
    };
    

    主要增加了一个失败指针,构建Ac自动机的过程 主要是将多个模式串构建成一个Trie树,并在其上构建失败指针(类似KMP的失效函数next数组)。

    还是之前描述过的,AC自动机是为了减少模式串的匹配次数,每次Trie树中的模式串失配之后不需要从Trie的root节点重新开始匹配,而是跳转到下一个可能匹配的模式串的指定位置继续匹配,这个位置就是由失败指针来控制的。

    举个例子:

    一下Trie树为模式串构建的,包含字符串abcd, bcf, c

    image-20210210101354513

    有一个从 从abcd字符串中C 指向bcf中的c 的指针,当我们在abcd中 d处匹配失效的时候可以继续从bcf 开始匹配,因为之前的bc已经在主串中存在了,所以不需要再从b开始进行匹配了。

    image-20210210101636165

    2.1 构建失败指针

    前面的例子 能够对失败指针在Trie树中的匹配作用有一个整体的了解,会减少Trie树中的匹配次数。

    注意,Ac自动机的场景是在一个主串中匹配多个模式串,一般用于敏感词过滤,匹配的过程就是减少在模式串中构成的Trie树的匹配次数。

    在KMP算法构建失效函数的过程中提到了一个最长可匹配前缀子串,因为KMP是从左向右匹配,所以在遇到坏字符的时候每次模式串的滑动需要滑动大最长可匹配前缀子串的位置。这里也是类似的,可以看到如上例子: 模式串匹配到abcd的d字符时 发现和主串的f不匹配,这个时候c为失效指针起作用的位置,即在abc是已经和主串达成匹配的字符串了,只需要找到abc中的最长可匹配后缀子串即可。

    后缀子串 就是最后一个字符串相同的子串,比如 abc 的后缀子串是 c, bc;最长可匹配后缀子串就是 Trie树中的其他字符串能够和bc匹配的前缀子串,比如案例中的bcf字符串 ,其前缀子串为b,bc ,则bc最长且和abc的后缀子串匹配。所以只需要让每一个失败指针保证指向的是最长可匹配后缀子串的结束位置即可。

    可以像kmp算法那样,当我们要求某个节点的失败指针的时候,可以通过已经求得的、深度更小的节点的失败指针来推导,从而能够逐层求解每个节点的失败指针,也就是失败指针的构建会层次遍历Trie树。

    构建失效指针的过程如下:

    变更案例Trie树如下

    image-20210210103428090

    其中root节点的失败指针为null,假设我们知道了字符c对应的TrieNode p的失败指针为 q,那我们想要求p的子节点pc的失败指针。如果pc->data == qc->data,即p的子节点字符和q的子节点字符相同,则将节点pc的失败指针指向qc, pc->fail = qc

    如果节点q没有子节点 或 q的子节点字符和pc的字符不想等,则让q = q->fail,再看看q的子字符是否和pc的字符相等,依次直到q==root,也就是找不到子节点和pc匹配的节点,就让pc->fail=root就好了。

    image-20210210110211432

    构建的过程需要层次遍历Trie树,依赖当前节点的上一个节点构建失败指针,将处于当前层的所有失败指针都构建完成。

    // Build the fail pointer in trie node.
    // The process is just like the next array in kmp alg.
    void Trie::bfsBuildFailPointer() {
      queue<AcNode*> Q;
      // Init the root fail pointer
      root_->fail = nullptr;
      Q.push(root_);
    
      while (!Q.empty()) {
        // Get the first element from queue, the element will be 
        // removed later
        AcNode *tmp = Q.front();
        Q.pop();
        // Build the fail pointer relationship with ervery children_
        for (int i = 0;i < 26; i++ ) {
          AcNode *pc = tmp->children_[i];
          if (pc == nullptr) {
            continue;
          }
    
          if (tmp == root_) {
            pc->fail = nullptr;
          } else {
            // Check the tmp's children_ pc and q's children_ qc
            // if they have the same char ,then  pc -> fail = qc
            // Or, q while back to last fail pointer
            AcNode *q = tmp->fail;
            while(q != nullptr) {
              AcNode *qc = q->children_[pc->data_ - 'a'];
              if (qc != nullptr) {
                pc -> fail = qc;
                break;
              }
    
              // Let the fail pointer move forward
              // Until the q->data_ == qc -> data_
              //
              // Just like the getNext in kmp, k = next[k],
              // util you find the des[k+1] == des[i+1].
              // Then you can make sure you have find the best 
              // prefix in current string.
              q = q->fail;
            }
    
            // qc's char is not equal with pc'c char in all q's fail pointer
            // keep pc's fail pointer to root_
            if (q == nullptr) {
              pc -> fail = root_;
            }
          }
    
          Q.push(pc);
        }
      }
    }
    

    2.2 依赖失败指针过滤敏感词

    有了失败指针的完整位置,也就知道了能够快速匹配的捷径。

    如下已经完成了所有节点失败指针构建的 Trie树
    image-20210210110211432

    主串为 abcdhe

    匹配过程中 输入的主串从 i=0开始,AC自动机从指针 p=root开始,假设主串是b

    • case1: 如果p指向的节点 的一个子节点x的字符串 等于b[i],我们就更新p指向x。同时,通过其p的一系列失败指针,检查以失败指针为结尾的路径是否是模式串(是否是被打上了ending标记,这个标记是在构建trie树是标识每个模式串的结束)。处理完成之后,i++, 继续这两个过程。
    • case2: 如果p 指向的节点没有等于b[i]字符的子节点,可以通过失败指针检查以该字符结尾的其他模式串是否有等于b[i]字符的子节点,并重复这两个过程。

    abcdhe 为主串的匹配过程可以带入以上两个case, 非常容易理解。

    以下逻辑为匹配模式串并输出 模式串在主串中的起始位置,并且完成模式串在主串中的替换:

    // Match the des string with fail pointer 
    void Trie::match(string des) {
      AcNode *p = root_;
      int des_len = des.size();
      int i;
      vector<pair<int,int>> match_vec;
    
      for (i = 0;i < des_len; i++) {
        int index = des[i] - 'a';
        // case2: try to match the des[i],if failed,traverse
        // fail pointer
        while(p->children_[index] == nullptr && p != root_) {
          p = p->fail;
        }
    		
        // find a char match with des[i]
        p = p->children_[index];
        if (p == nullptr) {
          p = root_;
        }
    
        AcNode *tmp = p;
        // Keep the tmp is not nullptr
        // case1: check the des[i]'s fail pointer ,if the fail pointer
        // is endingchar, and we will know that we have find a matching
        // string, record it.
        while(tmp != nullptr && tmp != root_) {
          if (tmp->isEndingChar_ == true) {
            int pos = i - tmp->length_ + 1;
            cout << "pos: " << pos << " len :" 
              << tmp -> length_ << endl;
            match_vec.push_back(make_pair(pos, tmp->length_));
          }
          tmp = tmp -> fail;
        }
      }
    
      // Below is to output the replace result in with match str 
      // in trie tree.
      if (match_vec.size() == 0) {
        cout << "string : " << des << 
          " has no match str in trie tree!" << endl;
        return;
      }
    
      int j = 0;
      int tmp;
      i = match_vec[j].first;
      while(i < des_len && j < match_vec.size()) {
        tmp = match_vec[j].second;
        while(tmp --) {
          des[i++] = '*';
        }
        j++;
      }
      cout << "string : " << des << " match !" << endl;
    }
    

    3. 复杂度及完整代码

    • 时间复杂度:

      • 构建Trie树的时间复杂度是O(m*len),len表示敏感词的平均长度,m表示敏感词的个数

      • 构建失败指针的复杂度:构建时 需要循环q = q->fail,这里每一次q指向的节点深度都会减1,也就是不会循环超过len次,。假设Trie树中总共k个节点,则每个节点构建失败指针的时间复杂度是O(len) ,总共O(k*len)次。

        需要注意的是AC自动机会预先构建好,并不会频繁更新。

      • AC自动机匹配主串时的复杂度,match函数中的两个while循环需要遍历当前节点的失败指针,时间复杂度为O(len),而外层的for循环时主串的长度,也就是O(n*len),因为敏感词其实都是一些短词语,实际上时间复杂度接近于O(n)。

    • 空间复杂度的话,也就是之前说的Trie的内存消耗,本来也就很大,对于每一个节点都会消耗26个AcNode 的空间,这里有一些构建Trie树时的时间和空间消耗的Trad-off 优化。

    完整代码:

    https://github.com/BaronStack/DATA_STRUCTURE/blob/master/string/ac_alg.cc

    总的来说,AC自动机在敏感词过滤的场景性能非常高效,但是由于Trie树带来的存储空间的消耗缺不可避免,不过整个算法实现思想还是非常有趣的。

    展开全文
  • KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体...
  • 背景在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下for (String document : documents) {for (String ...
  • 紧接着上一篇文章字符串匹配1,在上一篇文章里,我们主要总结归纳的是一个字符串和另一个字符串相比较。这篇文章,南国总结归纳的是两种常见的多模式匹配算法Trie树和AC自动机 多模式匹配:一个主串和多个模式串中间...
  • 字符串匹配算法(多模式串)

    千次阅读 2019-02-23 22:35:40
    上一篇了解了单模式串匹配算法,现在来学习多模式串匹配算法,首先需要了解TrieTrie树的概念 Trie树也叫字典树或者前缀树,它是一个树形的结构。是一种专门用来处理字符串匹配的数据结构,用来解决在一组字符串中...
  • | 导语 字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。所以算法的总运行时间为预处理和匹配的时间的总和。 1.明确你的目标是算法选择最重要的事 文本匹配算法有很多,按照匹配模式串...
  • 字符串匹配算法

    2019-12-17 10:30:38
    主要算法:BF RK BM KMP Sunday算法 BF :Brute Force,暴力匹配算法 字符串A中查找字符串B 主串:A,长度n 模式串:B,长度m 检查起始位置分别是0,1,2...BF为什么是一个很常用的字符串匹配算法? 1)实际场景中,n...
  • 今天就来谈一谈一些字符串匹配算法。先来说说大名鼎鼎的KMP算法,这个算法出现在无数的数据结构与算法书上面。它的策略很简单:当模式串第k个字符不匹配主串中第s时,我们其实己经知道了主串中s个字符前的k-1个字符...
  • 一、诞生原因 传统字符串比较时,需要将待比较的字符串...栗子:假如字符串集合中仅仅包含 26 个英文字母并且都为小写,那么该字符串集合组成的 Trie 树的部分如下图所示: 每个节点实际上是一个包含 26 个元素的数
  • 基于DoubleArray Trie的Aho-Corasick字符串匹配算法的Node实现。 安装 npm install aho-corasick-node --save 用法 建造 const AhoCorasick = require ( 'aho-corasick-node' ) ; const keywords = [ 'b' , 'ba' , ...
  • 多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于...
  • 当没有完全匹配的搜索结果,可以返回前缀最相似的可能。 例如三个单词app, apple, add,我们按照以下规则创建了一颗Trie树.对于从树的根结点走到黑色结点的路径上的字母依次组合起来就是一个完整的单词. class ...
  • 字符串匹配算法(单模式串)

    千次阅读 2019-02-17 22:37:22
    本文是数据结构与算法之美的学习笔记 字符串的匹配我们在平时工作中经常用到,每个语言中都有其对应的字符串的匹配方法,比如...多模式串匹配算法Trie树,AC自动机) BF(Brute Force)算法 基础概念:如果我...
  • 一、单模式串匹配 1、BF:简单粗暴,主串和模式串都不太长,时间复杂度为 O(m*n) 。 2、KP:字符集范围不要太大且模式串不要太长, 否则 hash 值可能冲突,时间复杂度为 O(n) 。 3、naive-BM:模式串最好不要太长...
  • 我们用的最多的就是编程语言提供的字符串查找函数,比如Java中的 indexOf(),Python 中的find()函数等,它们底层就是依赖接下来要讲的字符串匹配算法字符串匹配算法很多,我会分四节来讲。今天讲两种比较简单的...
  • 理论分析表明,HashTrie算法的空间复杂度为O(|P|),与模式串集合的规模|P|线性相关,与字符集大小σ无关,优于经典多模式串匹配算法AC的空间复杂度O(|P|σlog|P|)。在随机数据集和真实数据集(Snort、ClamAV和URL)...
  • Trie树,也叫“字典树”,是一种树形结构,专门用来处理字符串匹配的数据结构。 Trie树的本质,利用字符串间的公共前缀,将重复的字符合并在一起,形成一个树形结构,并且给叶子节点打上标记。其中,根节点不包含...
  • 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : documents) { for (String ...
  • 我们用的最多的就是编程语言所提供的字符串查找函数,比如 Java 中的 indexOf(),Python 中的 find() 函数等,它们底层就是依赖字符串匹配算法字符串匹配算法很多,两种比较简单的、比较好理解的是:BF 算法和 RK ...
  • 字符串匹配算法:BF算法和RK算法,都是单模式串匹配算法,即一个串和另一个串进行匹配,BM算法和KMP算法是多模式串匹配算法,即一个串种同时查找多个串,分别是Trie树和AC自动机 RK算法是BF算法的改进,RK算法是如何...
  • 字符串匹配算法之Aho-Corasick 字符串匹配算法之Aho-Corasick_我思故我在_百度空间字符串匹配算法之Aho-Corasick2008-12-18 16:23Aho-Corasick可以认为是KMP算法在多串查找的扩展。先把所有要查找的串...
  • KMP(字符串匹配),Trie树(字典树),manacher(最长回文子串) 算法思想 代码 经典题目
  • 字符串匹配算法——javascript 文章目录字符串匹配算法——javascript字符串匹配BF算法 (暴力匹配) √KMP算法 √BM算法**坏字符规则**好后缀规则Trid树(字典树)√ 字符串匹配 字符串匹配问题的形式定义: **...
  • Trie树之Golang代码简释

空空如也

空空如也

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

字符串匹配算法trie