Aho_Corasick.hpp

Go to the documentation of this file.

/*
 *  Copyright 2009 DreamLab Onet.pl Sp. z o.o.
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *  http://www.apache.org/licenses/LICENSE-2.0
 *
 *   Unless required by applicable law or agreed to in writing, software
 *   distributed under the License is distributed on an "AS IS" BASIS,
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *   See the License for the specific language governing permissions and
 *   limitations under the License.
 *
 *   Authors:
 *   Michal Szklarzewicz <michal(x)szklarzewicz(y)gmail(x)com>
 *   Grzegorz Jablonski  <jablonski(x)grzegorz(y)gmail(x)com>
 *   (use dot instead of x, and @ instead of y)
 */

#ifndef __AHO_CROASICK_HPP__INCLUDED__
#define __AHO_CROASICK_HPP__INCLUDED__

#include <map>
#include <algorithm>
#include <deque>
#include "types.hpp"

template<class Type>
class Aho_Corasick
{

    public:
        Aho_Corasick() {
            root = new TrieNode;
        }
        ~Aho_Corasick() {
            delete root;
        }
                void clean() {
                        delete root;
                        root = new TrieNode;
                }
        void add_pattern(const t_uid &patternId, int count, Type data[]); // builds Trie using pattern
                void remove_pattern(int count, Type data[]); // remove (and free if needed) pattern
        void commit_trie(); // commits Trie, must be used before find_patterns call and after all add_patern calls
        bool find_patterns(int count, Type textData[], bool(*CallbackProc)(const t_uid&,int,void*), void* context); // finds patterns in text and calls CallbackProc for each result

    private:
        struct TrieNode
        {
            std::map<Type,TrieNode*> children;
            TrieNode* accept;
            TrieNode* pi;
            t_uid patternId;
            int patternSize;
                        bool accept_copy;

            TrieNode() {
                                accept_copy = true;
                accept = 0;
                pi = 0;
                patternId.length = 0;
                patternSize = 0;
            }
            ~TrieNode() {
            typename std::map<Type, TrieNode* >::iterator it = this->children.begin();
            while(it != this->children.end()) {
                delete it->second;
                it++;
                }
            this->children.clear();
            }
        };

        TrieNode* root;
};

template<class Type>
void Aho_Corasick<Type>::add_pattern(const t_uid &patternId, int count, Type data[]) {
    TrieNode* curr = this->root;
    for(int x=0;x<count;++x) {
        typename std::map<Type, TrieNode* >::iterator it = curr->children.find(data[x]);
        if(it == curr->children.end()) {
            TrieNode* tmp = new TrieNode;
            curr->children[data[x]] = tmp;
            curr = tmp;
        } else {
            curr = it->second;
        }
    }
    curr->accept = curr;
    curr->patternId = patternId;
    curr->patternSize = count;
        curr->accept_copy = false;
}

template<class Type>
void Aho_Corasick<Type>::remove_pattern(int count, Type data[]) {
    TrieNode* curr = this->root;
        
        std::deque<TrieNode*> find_stack;
        
    for(int x=0;x<count;++x) {
        typename std::map<Type, TrieNode* >::iterator it = curr->children.find(data[x]);
        if(it == curr->children.end()) {
            return; //already deleted or error
        } else {
                        find_stack.push_back(curr);
            curr = it->second;
        }
    }
        
        curr->accept_copy = true; // will be removed by next commit
        
        //unwind trie (remove corrupted branch)
        while(find_stack.size() > 1) { // root is there too, but not delete it 
                size_t n = find_stack.size() - 1;
                TrieNode* curr = find_stack.back();
                find_stack.pop_back();
                
                if(curr->children.size() > 0) {
                        break; // more children to go
                }
                TrieNode* parent = find_stack.back();
                parent->children.erase(data[n]);
                
                delete curr;
        }
}

template<class Type>
void Aho_Corasick<Type>::commit_trie() {
        //set curr->accept = 0 for each accept_copy = true

    root->pi = this->root;
    std::deque<TrieNode*> Queue;
    Queue.push_back(root);

    while(Queue.size() != 0) {
        TrieNode* v = Queue.front();
        Queue.pop_front();
                
                if(v->accept_copy) {
                        v->accept = 0;
                }
                
        for(typename std::map<Type, TrieNode* >::iterator it = v->children.begin(); it != v->children.end(); ++it) {
            Queue.push_back(it->second);
                }
        }
        
    Queue.push_back(root);

    while(Queue.size() != 0) {
        TrieNode* v = Queue.front();
        Queue.pop_front();

        typename std::map<Type, TrieNode* >::iterator it = v->children.begin();
        while(it != v->children.end()) {
            if(v == root) {
                it->second->pi = root;
            } else {
                Type a = it->first;

                TrieNode* s = v->pi;
                typename std::map<Type, TrieNode* >::iterator it2 = s->children.find(a);
                while(s != this->root && it2 == s->children.end()) {
                    s = s->pi;
                    it2 = s->children.find(a);
                }
                if( it2 != s->children.end() ) {
                    s = it2->second;
                }
                it->second->pi = s;
                if(it->second->accept == 0) {
                    it->second->accept = s->accept;
                    it->second->patternId = s->patternId;
                    it->second->patternSize = s->patternSize;
                }
            }
            Queue.push_back(it->second);
            it++;
        }
    }
}

template<class Type>
bool Aho_Corasick<Type>::find_patterns(int count, Type textData[], bool(*CallbackProc)(const t_uid&,int,void*), void* context) {
        bool at_last_one_found = false;
        
    TrieNode* s = this->root;
    for(int i=0;i<count;++i) {
        typename std::map<Type, TrieNode* >::iterator it = s->children.find(textData[i]);
        while( s!=this->root && it == s->children.end()) {
            s = s->pi;
            it = s->children.find(textData[i]);
        }
        if( it != s->children.end()) {
            s = it->second;
        }

        TrieNode* tmp = s->accept;
        while(tmp != 0) {
                        at_last_one_found = true;
                        
            if(!CallbackProc(tmp->patternId,i-tmp->patternSize+1, context)) {
                                return true;
                        }
            tmp = tmp->pi->accept;
        }
    }
        return at_last_one_found;
}

#endif

---