ExperimentalCompactSuffixAutomatonConstruct.h

Go to the documentation of this file.

 
#include <indexes/stringology/CompactSuffixAutomatonTerminatingSymbol.h>
#include <string/LinearStringTerminatingSymbol.h>
#include <alphabet/EndSymbol.h>
#include <string/LinearString.h>
 
namespace stringology {
 
namespace indexing {
 
class ExperimentalCompactSuffixAutomatonConstruct {
 
    template <class SymbolType>
    class CompactSuffixAutomatonConstructInt {
        int nil;
        int newVertexNumber;//hodnota použitá při vytvoření nového vrcholu
        int e;
        int T;//T == ┴
        int source;
        int sink;
        int m; //velikost abecedy
        ext::map<int,SymbolType> w; //slovo, kde na indexech -m až -1 je abeceda
        int wLen;//délka slova w
        SymbolType endChar;//znak, kterým končí řetězec - unikátní v celém řetězci. V článku $
 
        //         vrchol  popis-hrany koncový-vrchol
        //         v            v     v
        ext::map<int,ext::map<ext::pair<int,int>,int>> edges;
        ext::map<int,int> suf;
        ext::map<int,int> length;
 
        int createNode() {
            edges.insert({newVertexNumber,ext::map<ext::pair<int,int>,int>()});
            return newVertexNumber++;
        }
 
        void createEdge(int fromVertex, int first, int second, int toVertex) {
            edges.at(fromVertex).insert({{first, second},toVertex});
        }
 
        //hledání w[k]-edge. Použito na několika místech v algoritmu.
        //char c je w[k]
        void wkEdge(int s, const SymbolType & c, int & sc, int & kc, int & pc) {
            for ( const std::pair < const ext::pair < int, int >, int > & edge : edges.at ( s ) ) {
                if ( w.at ( edge.first.first ) == c) {
                    sc = edge.second;
                    kc = edge.first.first;
                    pc = edge.first.second;
                    return;
                }
 
            }
            throw "neniHrana";
        }
 
        //pomocná funkce, která reprezentuje řádek 3 ve funkci split_edge()
        void replaceTheEdgeBy(int s, int k, int p, int sc, int kc, int pc, int r) {
            edges.at(s).erase({kc,pc});
 
            createEdge(s,kc,kc+p-k,r);
            createEdge(r,kc+p-k+1,pc,sc);
        }
 
        //pomocná funkce ve funkci redirect_edge řádek 2
        void replaceTheEdgeByEdge(int s, int k, int p, int kc, int pc, int r) {
            edges.at(s).erase({kc,pc});
 
            createEdge(s,kc,kc+p-k,r);
        }
 
        //pomocná funkce ve funkci separate_node řádek 9
        void replaceThewkEdge(int s, int k, int p, int rc) {
            int kcc;
            int scc;
            int pcc;
            wkEdge(s,w.at(k),scc,kcc,pcc);
 
            edges.at(s).erase({kcc,pcc});
            createEdge(s,k,p,rc);
        }
 
        //pomocná funkce, která reprezentuje řádek 4 ve funkci check_end_point
        bool thereIsACedgeFromS(int s, const SymbolType & c) {
            //procházím hrany vrcholu s a hledám, jestli se první znak hrany rovná c
            for ( const std::pair < const ext::pair < int, int >, int > & edge : edges.at ( s ) )
                if ( w.at ( edge.first.first ) == c )
                    return true;
 
            return false;
        }
 
        //tvoří kopii vrcholu. (Překopíruje hrany)
        int duplicationOf(int sc) {
            int rc = createNode();
 
            for ( const std::pair < const ext::pair < int, int >, int > & edge : edges.at ( sc ) )
                createEdge ( rc, edge.first.first, edge.first.second, edge.second );
 
            return rc;
        }
 
        //konec pomocných funkcí. Dále je co nejpřesnější přepis pseudokodu
 
        bool check_end_point(int s,int k,int p, const SymbolType & c) {
            if(k<= p) {
                int sc;
                int kc;
                int pc;//s' k' p'
                wkEdge(s,w.at(k),sc,kc,pc);
                return (c == w.at(kc+p-k+1));
            }
            return thereIsACedgeFromS(s,c);
        }
 
        int split_edge(int s,int k,int p) {
            int sc;
            int kc;
            int pc;//s' k' p'
            wkEdge(s,w.at(k),sc,kc,pc);
 
            int r = createNode();
            replaceTheEdgeBy(s,k,p,sc,kc,pc,r);
 
            int len = length.at(s);
            if(len == INT_MAX)
                len = e;
 
            length[r] = len + (p-k+1);
            return r;
        }
 
        ext::pair<int,int> canonize(int s,int k,int p) { //p se může rovnat e
            if(k>p)
                return ext::make_pair ( s, k );
 
            int sc;
            int kc;
            int pc;
            wkEdge(s,w.at(k),sc,kc,pc);
 
            if(pc == INT_MAX)
                pc = e;
 
            while(pc-kc <= p-k) {
                k = k+pc-kc+1;
                s = sc;
                if(k<=p) {
                    wkEdge(s,w.at(k),sc,kc,pc);
                    if(pc == INT_MAX)
                        pc = e;
                }
            }
            return ext::make_pair ( s, k );
        }
 
        void redirect_edge(int s, int k, int p, int r) {
            int sc;
            int kc;
            int pc;
            wkEdge(s,w.at(k),sc,kc,pc);
 
            replaceTheEdgeByEdge(s,k,p,kc,pc,r);
        }
 
        int extension(int s, int k, int p) {
            if(k > p)
                return s;
 
            int kc;
            int pc;
            int sc;
            wkEdge(s,w.at(k),sc,kc,pc);
            return sc;
        }
 
        ext::pair<int,int> separate_node(int s,int k,int p) { //p==e
            int sc;
            int kc;
            ext::tie ( sc, kc ) = canonize(s,k,p);
            if ( kc <= p)
                return ext::make_pair ( sc, kc );
 
            int len = length.at(s);
            if(len == INT_MAX)
                len = e;
 
            int lensc = length.at(sc);
            if(lensc == INT_MAX)
                lensc = e;
 
            if(lensc == len+(p-k+1))
                return ext::make_pair ( sc, kc );
 
            int rc = duplicationOf(sc);
            suf[rc] = suf.at(sc); suf[sc] = rc;
            length[rc] = len +(p-k+1);
            do {
                replaceThewkEdge(s,k,p,rc);
 
                ext::tie ( s, k ) = canonize(suf.at(s),k,p-1);
            } while ( ext::make_pair ( sc, kc ) == canonize(s,k,p));
 
            return ext::make_pair ( rc, p+1 );
        }
 
        ext::pair<int,int> update(int s,int k,int p) {
            const SymbolType & c = w.at(p);
            int oldr = nil;
 
            int sc = nil; // v článku není s' inicializované, ale je potřeba to na něco inicializovat, protože níže dochází k porovnávní
            int r = -1; // not initialized in the paper. The first comparison of sc must fail and therefore variable r will neverbe read with its initial value
            while(!check_end_point(s,k,p-1,c)) {
                if(k<= p-1) {
                    if(sc == extension(s,k,p)) {
                        redirect_edge(s,k,p-1,r);
                        ext::tie ( s, k ) = canonize(suf.at(s),k,p-1);
                        continue;
                    } else {
                        sc = extension(s,k,p);
                        r = split_edge(s,k,p-1);
                    }
                } else
                    r = s;
 
                createEdge(r,p,INT_MAX,sink); //p == e vždy. p je nahrazeno INT_MAX
 
                if(oldr != nil)
                    suf[oldr] = r;
                oldr = r;
 
                ext::tie ( s, k ) = canonize(suf.at(s),k,p-1);
            }
 
            if(oldr != nil)
                suf[oldr] = s;
            return separate_node(s,k,p);
        }
 
    public:
        CompactSuffixAutomatonConstructInt ( const /*string::LinearString*/ext::vector < SymbolType > & subject ) : wLen ( subject.size ( ) ), endChar ( subject.back ( ) ) {
            nil = INT_MIN;
            newVertexNumber = -1;
            ext::set < SymbolType > alphabet ( subject.begin ( ), subject.end ( ) );
 
            for ( int i = 0; i < wLen; ++ i )
                w.insert ( std::make_pair ( i + 1, subject [ i ] ) );
 
            m = alphabet.size();
 
            int i = -1;
            for ( const SymbolType & symbol : alphabet )//abecedu je potřeba vyskládat na záporné indexy od -1 do -m
                w.insert ( std::make_pair ( i --, symbol ) );
        }
 
        void startConstruction() {
            T = createNode();
            source = createNode();
            sink = createNode();
            for(int j = 1;j<=m;j++)
                createEdge(T,-j,-j,source);
            suf[source] = T;
            length[source] = 0; length[T] = -1;
            e = 0; length[sink] = INT_MAX;
 
            int s = source;
            int k = 1;
            int i = 0;
            do {
                i = i+1; e = i;
                ext::tie ( s, k ) = update ( s, k, i );
                //print ( i );
            } while (w.at(i) != endChar);
        }
 
        void print ( int i ) const {
            std::cout << "Krok " << i << std::endl;
            for(int pi = 0;pi<newVertexNumber;pi++) {
                std::cout << "Vrchol " << pi << std::endl;
                for(ext::map<ext::pair<int,int>,int>::const_iterator it = edges.at(pi).begin(); it != edges.at(pi).end(); ++it) {
                    std::cout << it->first.first << " " << it->first.second;
                    std::cout << "     -- ";
                    for(int j = it->first.first;j<=it->first.second;j++) {
                        if(j>i) break;
                        std::cout << w.find(j)->second;
                    }
                    std::cout << " --> " << it->second << std::endl;
                }
            }
 
            std::cout << "-------------" << std::endl;
 
            std::cout << "Delky" << std::endl;
            for(int pi = 0;pi<newVertexNumber;pi++)
                std::cout << "Vrchol " << pi << " " << length.find(pi)->second << std::endl;
 
            std::cout << "Suffix links" << std::endl;
            for(int pi = 0;pi<newVertexNumber;pi++)
                std::cout << "Vrchol " << pi << " " << suf.find(pi)->second << std::endl;
        }
 
        void changeIntMaxToE() {
            for(auto it = edges.begin();it!=edges.end();++it)
                for(auto it2 = it->second.begin();it2!=it->second.end();++it2)
                    if(it2->first.second == INT_MAX) {
                        int k = it2->first.first;
                        int r = it2->second;
 
                        it->second.erase(it2);
                        it->second.insert({{k,e},r});
                        it2 = it->second.begin();
                    }
        }
 
        const ext::map<int,ext::map<ext::pair<int,int>,int>> & getEdges ( ) const {
            return edges;
        }
    };
 
public:
    static indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < DefaultSymbolType > construct ( const string::LinearStringTerminatingSymbol & subject ) {
        CompactSuffixAutomatonConstructInt < DefaultSymbolType > algo (subject.getContent ( ) );
        algo.startConstruction();
        algo.changeIntMaxToE();
        //algo.print ( subject.getContent().size ( ) );
 
        indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < DefaultSymbolType > res;
        res.setString(subject.getContent ( ) );
        res.setNumberOfVertices(algo.getEdges().size()-1);
 
        for ( const auto & edge : algo.getEdges ( ) )
            if ( edge.first != -1 )
                res.insertVertex ( edge.first, edge.second );
 
        return res;
    }
 
    template < class SymbolType >
    static indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > construct ( const string::LinearString < SymbolType > & subject ) {
        SymbolType endSymbol = common::createUnique ( alphabet::EndSymbol::instance < SymbolType > ( ), subject.getAlphabet ( ) );
        ext::vector < SymbolType > content = subject.getContent ( );
        content.push_back ( endSymbol );
 
        CompactSuffixAutomatonConstructInt < SymbolType > algo ( content );
        algo.startConstruction();
        algo.changeIntMaxToE();
        //algo.print ( subject.getContent().size ( ) );
 
        indexes::stringology::CompactSuffixAutomatonTerminatingSymbol < SymbolType > res;
        res.setString ( content );
        res.setNumberOfVertices(algo.getEdges().size()-1);
 
        for ( const auto & edge : algo.getEdges ( ) )
            if ( edge.first != -1 )
                res.insertVertex ( edge.first, edge.second );
 
        return res;
    }
};
 
} /* namespace indexing */
 
} /* namespace stringology */