_SuffixArrayScanningBase.cpp

Go to the documentation of this file.

#include "_SuffixArrayScanningBase.h"
#include <iostream>

using namespace std;

C_SuffixArrayScanningBase::C_SuffixArrayScanningBase()
{
        this->countOfCountsTable = 0;   //no memory has been allocated
        this->maxFreqConsidered = 1000; //for freq >1000, no need to discount, MLE is good enough
}

C_SuffixArrayScanningBase::C_SuffixArrayScanningBase(const char * filename, unsigned int maxN)
{
        this->countOfCountsTable = 0;  //no memory has been allocated
        this->maxFreqConsidered = 1000; //for freq >1000, no need to discount, MLE is good enough

        //load suffix array
        this->loadData(filename, false, true, true);

        this->initializeForScanning(filename, maxN);
}

void C_SuffixArrayScanningBase::setParam_maxFreqConsidered(int maxFreqConsidered)
{
        this->maxFreqConsidered = maxFreqConsidered;
}


void C_SuffixArrayScanningBase::initializeForScanning(const char * filename, unsigned int maxN)
{
        this->maxN = maxN;
        this->nGramScanningList = (S_nGramScanningInfoElement *) malloc(sizeof(S_nGramScanningInfoElement)*this->maxN);
        this->countOfCountsTable = 0;   //no memory has been allocated

        //initialize the scanning list
        for(int i=0;i<this->maxN;i++){
                this->nGramScanningList[i].freqSoFar=0;
                this->nGramScanningList[i].vocId = 0;
                this->nGramScanningList[i].freqThreshForOutput = (unsigned int) -1;     //default, do not output
        }

        //get vocID for sentEnd
        this->vocIdForSentEnd = this->voc->returnId(C_String("_END_OF_SENTENCE_"));

        if(this->vocIdForSentEnd==0){
                cerr<<"VocID for _END_OF_SENTENCE_ can not be found. Critical error.\n";
                exit(0);
        }

        this->vocIdForSentStart = this->voc->returnId(C_String("_SENTENCE_START_"));
        if(this->vocIdForSentStart==0){
                cerr<<"VocID for _SENTENCE_START_ can not be found. Critical error.\n";
                exit(0);
        }
        
        this->vocIdForCorpusEnd = this->voc->returnId(C_String("_END_OF_CORPUS_"));
        if(this->vocIdForCorpusEnd==0){
                cerr<<"VocID for _END_OF_CORPUS_ can not be found. Critical error.\n";
                exit(0);
        }
}

C_SuffixArrayScanningBase::~C_SuffixArrayScanningBase()
{
        free(this->nGramScanningList);

        if(this->countOfCountsTable!=0){
                free(this->countOfCountsTable);
        }

}

void C_SuffixArrayScanningBase::setNgramOutputFreqThresh(int n, unsigned int freqThresh)
{
        if(n>this->maxN){
                cerr<<"Illegal operation.n="<<n<<" is greater than maxN="<<this->maxN<<endl;
                exit(0);
        }

        this->nGramScanningList[n-1].freqThreshForOutput = freqThresh;
}

void C_SuffixArrayScanningBase::scanSuffixArrayForHighFreqNgramType()
{
        this->scanSuffixArray('H');

}

void C_SuffixArrayScanningBase::scanSuffixArrayForCountofCounts(int maxFreqConsidered)
{
        this->maxFreqConsidered = maxFreqConsidered;
        this->constructCountOfCountsTable();
        
        //output the count of counts
        cout<<this->maxN<<"\t"<<maxFreqConsidered<<endl;
        for(int i=0;i<this->maxN;i++){
                cout<<i+1<<endl;
                
                unsigned int * ccTableForThisN = this->countOfCountsTable + i*maxFreqConsidered;
                for(int freq=0;freq<maxFreqConsidered;freq++){
                        cout<<freq+1<<"\t"<<ccTableForThisN[freq]<<endl;
                }
        }
        
}

void C_SuffixArrayScanningBase::scanSuffixArrayForTypeToken()
{
        this->typeFreq = (unsigned int *) malloc(sizeof(unsigned int)*maxN);
        this->tokenFreq = (unsigned int *) malloc(sizeof(unsigned int)*maxN);

        //initialize
        for(int n=0;n<maxN;n++){
                this->typeFreq[n]=0;
                this->tokenFreq[n]=0;
        }


        //scan the suffix array
        this->scanSuffixArray('T');

        //output
        cout<<"n\tType\tToken\n";
        for(int i=0;i<this->maxN;i++){
                cout<<i+1<<"\t"<<typeFreq[i]<<"\t"<<tokenFreq[i]<<endl;
        }
}

void C_SuffixArrayScanningBase::constructCountOfCountsTable()
{
        if(this->countOfCountsTable!=0){        //if there is already a count of counts table
                free(this->countOfCountsTable);
        }

        this->countOfCountsTable = (unsigned int *) malloc(sizeof(unsigned int)*this->maxN*this->maxFreqConsidered);

        if(this->countOfCountsTable==NULL){
                cerr<<"Count of counts table can not be initialized. Exit\n";
                exit(0);
        }

        for(int c=0;c<this->maxN*this->maxFreqConsidered;c++){
                this->countOfCountsTable[c]=0;
        }

        this->scanSuffixArray('C');


}

void C_SuffixArrayScanningBase::scanSuffixArray(char actionType)
{
        
        int i,j;
        bool stillMeaningful = true;    
        TextLenType saPos=0;

        while(stillMeaningful && ( saPos<this->corpusSize ) ){

                TextLenType posInCorpus = this->suffix_list[saPos];
                IndexType wordInCorpus = this->corpus_list[posInCorpus];

                if(wordInCorpus<this->sentIdStart){     //SA positions pointing to sentID are not interesting
                        
                        if((wordInCorpus!=this->vocIdForSentStart)&&(wordInCorpus!=this->vocIdForSentEnd)&&(wordInCorpus!=this->vocIdForCorpusEnd)){    //n-grams start with <s> and </s>, or <end of corpus> are not interested
                        
                                bool quit =false;
                                i=0;

                                while(!quit && (i<this->maxN)){
                                        wordInCorpus = this->corpus_list[posInCorpus+i];
                                        if(                                             
                                                (wordInCorpus<this->sentIdStart)&&
                                                (wordInCorpus!=this->vocIdForSentEnd)&&
                                                (wordInCorpus!=this->vocIdForSentStart)&&
                                                (wordInCorpus==this->nGramScanningList[i].vocId)){      //still match

                                                this->nGramScanningList[i].freqSoFar++;
                                        }
                                        else{   //we will have new (i+1) and longer n-grams soon, before that check if we should increase the count of counts for n because of this n-gram type
                                                                        
                                                bool validNgramUpSoFar = true;
                                                unsigned int freqSoFar;
                                                C_String tmpPhrase; //for output high freq n-grams

                                                //prepare the prefix of the n-grams
                                                if(actionType=='H'){
                                                        //common i-gram
                                                        for(j=0;j<=i-1;j++){
                                                                if(this->nGramScanningList[j].vocId==0){        //one of the word in the common i-gram is a NULL word, not a valid n-gram
                                                                        validNgramUpSoFar = false;
                                                                }
                                                                tmpPhrase.appending(this->voc->getText(this->nGramScanningList[j].vocId));
                                                                tmpPhrase.appending(C_String(" "));
                                                        }       
                                                }


                                                for(j=i;j<this->maxN;j++){                              
                                                        
                                                        
                                                        if(this->nGramScanningList[j].vocId==0){                //a NULL word, then this n-gram and longer ones in the scan window are invalid
                                                                validNgramUpSoFar = false;
                                                        }

                                                        if(validNgramUpSoFar){          //perform actions depends on actionType
                                                                
                                                                switch(actionType){

                                                                case 'C':       //count of counts
                                                                        freqSoFar = this->nGramScanningList[j].freqSoFar;
                                                                        if( (freqSoFar > 0) && ( freqSoFar <= this->maxFreqConsidered) ){
                                                                                //increase the count for (j+1)-gram with freq freqSoFar
                                                                                this->countOfCountsTable[j*this->maxFreqConsidered+freqSoFar-1]++;
                                                                        }
                                                                        break;

                                                                case 'H':       //output high-freq n-grams
                                                                        tmpPhrase.appending(this->voc->getText(this->nGramScanningList[j].vocId));
                                                                        tmpPhrase.appending(C_String(" "));

                                                                        if(this->nGramScanningList[j].freqSoFar>=this->nGramScanningList[j].freqThreshForOutput){                                                       
                                                                                cout<<tmpPhrase.toString()<<"\t"<<this->nGramScanningList[j].freqSoFar<<endl;
                                                                        }
                                                                        break;

                                                                case 'T':       //type-token statistics
                                                                        if(this->nGramScanningList[j].freqSoFar>0){
                                                                                typeFreq[j]++;
                                                                        }

                                                                        tokenFreq[j]+=this->nGramScanningList[j].freqSoFar;

                                                                        break;  
                                                                default: 
                                                                        cerr<<"Unknown action!\n";
                                                                        exit(-1);
                                                                }
                                                        }

                                                        //finished output, now clear the list from point of i
                                                        if((posInCorpus+j)<this->corpusSize){
                                                                wordInCorpus = this->corpus_list[posInCorpus+j];
                                                        }
                                                        else{
                                                                wordInCorpus = 0;       //out of bound for corpus
                                                        }

                                                        if((wordInCorpus==0)||(wordInCorpus>=this->sentIdStart)||(wordInCorpus==this->vocIdForSentEnd)||(wordInCorpus==this->vocIdForSentStart)){
                                                                wordInCorpus=0; //write 0 for <sentId>, <s> and </s>
                                                                this->nGramScanningList[j].freqSoFar = 0;
                                                        }
                                                        else{
                                                                this->nGramScanningList[j].freqSoFar = 1;
                                                        }

                                                        this->nGramScanningList[j].vocId = wordInCorpus;                                                        
                                                }

                                                quit=true;      //at i+1 gram, already not match, no need to check for longer
                                        }

                                        i++;
                                }
                        }
                }
                else{
                        stillMeaningful = false;        //once vocID is getting larger/equal than sentIdStart, everything follows it are <sentId> and no actual text
                }

                saPos++;
        }

        //at the end of corpus (according to suffix order)
        C_String finalTmpString;        //for output high-freq n-gram type
        bool validNgramUpSoFar = true;
        unsigned int freqSoFar;
        for(i=0;i<this->maxN;i++){
                if(this->nGramScanningList[i].vocId==0){        //invalide word
                        validNgramUpSoFar = false;
                }

                if(validNgramUpSoFar){
                        switch(actionType){
                        case 'C':       //for count-of-counts
                                freqSoFar = this->nGramScanningList[i].freqSoFar;
                                if( (freqSoFar > 0) && ( freqSoFar <= this->maxFreqConsidered) ){
                                        //increase the count for (i+1)-gram with freq freqSoFar
                                        this->countOfCountsTable[i*this->maxFreqConsidered+freqSoFar-1]++;
                                }
                                break;

                        case 'H':       //for high-freq n-gram types
                                finalTmpString.appending(this->voc->getText(this->nGramScanningList[i].vocId));
                                finalTmpString.appending(C_String(" "));
                                if(this->nGramScanningList[i].freqSoFar>this->nGramScanningList[i].freqThreshForOutput){                        
                                        cout<<finalTmpString.toString()<<"\t"<<this->nGramScanningList[i].freqSoFar<<endl;
                                }
                                break;

                        case 'T':       //for type-token statistics
                                if(this->nGramScanningList[i].freqSoFar>0){
                                        typeFreq[i]++;
                                }

                                tokenFreq[i]+=this->nGramScanningList[i].freqSoFar;
                                break;

                        default: 
                                cerr<<"Unknown action!\n";
                                exit(-1);
                        }
                }
        }

}

---