waptree.cpp

WAP树类似于FP-tree,是用于邻近序列模式的挖掘,可以作为相关算法改进的基础

                                }

                       }

                       if(!subPattern.empty())
                       {
                                middle<<endl;
                                middle<<subLength<<"\t" << subCount;
                                while( !subPattern.empty()){
                                        middle <<"\t" << subPattern.top();
                                        subPattern.pop();
                                }
                       }
                       linkTranversal = linkTranversal->nextLink;
                }
                middle.close();
                basePattern.push(i->event);
                BuildTree("middle.data", basePattern );
                basePattern.pop();
            }
       }
}



void BuildTree(char *sourceFile, stack<int> basePattern)
{

        bool OpenFile;
        int count;
	sequence seq, duplicate;

	//Next is Scan the database

        if (strcmp(sourceFile,"middle.data")==0)
		{
			// Build the condtional WAP tree
			runTime++;
                	//cout<<"Scan the intermediate database: " << runTime <<endl;
                	OpenFile = true;
        }
        else
        {
			// Build the original WAP tree
                	//cout<<"Scan the Original database.... " <<endl;
                	OpenFile = false;
        }

	ifstream ins ( sourceFile, ios::in);

	if ( !ins) {
		cerr << " File could not be opened\n";
		exit(1);
	}

	sequence::iterator point, eflag;
	int event, cid, number, seqNumber = 0;

	while (ins && !ins.eof())
	{
			// read the file and build the tree
                if(!OpenFile)
		    {
// read file from origional data file, read user id, event number from file
				ins >> cid;
                        ins >> number;
                        seqNumber++;
                        count = 1;
                }
                else
                {
				// read file from middle data file 
				ins >> number;
                        ins >> count;
                }

                duplicate.clear();

		    for(int i=0; i< number; i++)
                {
				ins >> event;

                        if ( duplicate.find(event) == duplicate.end())
                        {
        					duplicate.insert(sequence::value_type(event, 1));

	        				point = seq.find(event);
		        			eflag = seq.end();
			        
							if ( point != eflag)
	        					point ->second = point ->second + count;
        					else
	        					seq.insert( sequence::value_type(event,count));

						}
                }
	}

  // finish reading file, and next is going to filter out the event that does not meet the minimum support
        if (!OpenFile)
                frequency = (int)(minSupp* seqNumber);

        sequence::iterator i, bi;
        int n=0;

        for (  i = seq.begin(); i!=seq.end(); i++)
        {
                bi=i;
                if( bi != seq.begin())
                        bi--;
                else
                        bi= seq.begin();

                if (i->second < frequency)
                {
                        seq.erase(i);
                        i=bi;
                        n++;
                }
        }


        //cout<<"Finish scanning the database and Begin to build the tree ... " << endl;

	  // Next is build the WAP tree
        list<linkheader> lnkhdr;
        linkheader *newLinkHeader;
        bool newLink;
        node *Tranversal, *newNode, *Parent, *lastLinkage;
        node *root = new node;

        root->event = -1;
        root->occur = -1;
        root->parent = NULL;
        root->lSon = NULL;
        root->rSibling = NULL;
        root->nextLink = NULL;

        ifstream inFile ( sourceFile, ios::in);

	if ( !inFile) {
		cerr << " File could not be opened\n";
		exit(1);
	}

	while (inFile && !inFile.eof())
	{
		if ( !OpenFile)
                {
                        inFile >> cid;
                        inFile >> number;
                        count = 1;
                }
                else
                {
                        inFile >> number;
                        inFile >> count ;
                }

                Tranversal = root;

	  for(int i=0; i< number; i++)
        {
		//read event one by one, and insert the event into the tree
		    inFile >> event;

                    if(seq.find(event) != seq.end())
                    {
                        Parent = Tranversal;

                        list<linkheader>::iterator lnkBrow = lnkhdr.begin();
                        while (lnkBrow->event != event && lnkBrow != lnkhdr.end())
                               lnkBrow++;

                        if(lnkBrow == lnkhdr.end())
                                newLink = true;
                        else{
                                newLink = false;
                                lastLinkage = lnkBrow->lastLink;
                        }

                        if( Tranversal->lSon == NULL)
                        {
                                newNode = new node;
                                newNode->event = event;
                                newNode->occur = count;
                                newNode->lSon = NULL;
                                newNode->rSibling = NULL;
                                newNode->parent = Parent;
                                Tranversal->lSon = newNode;
                                if (newLink)
                                {
                                        newLinkHeader = new linkheader;
                                        newNode->nextLink=NULL;
                                        newLinkHeader->link = newNode;
                                        newLinkHeader->lastLink = newNode;
                                        newLinkHeader->event= event;
                                        lnkhdr.push_back(*newLinkHeader);
                                        free(newLinkHeader);
                                }
                                else
                                {
                                        lastLinkage->nextLink = newNode;
                                        lnkBrow->lastLink = newNode;
                                        newNode->nextLink = NULL;
                                }
                                Tranversal = newNode;
                        }
                        else
                        {
                                Tranversal = Tranversal->lSon;
                                if ( Tranversal->event == event)
                                        Tranversal->occur = Tranversal->occur + count;
                                else
                                {
                                        bool find= false;
                                        while(Tranversal->rSibling != NULL && !find )
                                        {
                                                Tranversal = Tranversal->rSibling;
                                                if ( Tranversal->event == event)
                                                {
                                                        Tranversal->occur = Tranversal->occur + count;
                                                        find = true;
                                                }
                                        }
                                        if (!find)
                                        {
                                                newNode = new node;
                                                newNode->event = event;
                                                newNode->occur = count;
                                                newNode->lSon = NULL;
                                                newNode->rSibling = NULL;
                                                newNode->parent = Parent;
                                                Tranversal->rSibling = newNode;
                                                if (newLink)
                                                {
                                                        newLinkHeader = new linkheader;
                                                        newNode->nextLink=NULL;
                                                        newLinkHeader->link = newNode;
                                                        newLinkHeader->lastLink = newNode;
                                                        newLinkHeader->event= event;
                                                        lnkhdr.push_back(*newLinkHeader);
                                                        free(newLinkHeader);
                                                }
                                                else
                                                {
                                                        lastLinkage->nextLink = newNode;
                                                        newNode->nextLink=NULL;
                                                        lnkBrow->lastLink = newNode;
                                                }
                                                Tranversal = newNode;
                                        }
                                }
                        }
                    }
                }
	}
        //cout<<"End of building tree and linkage..."<<endl;
        //cout<<"\n\nBegin the mining process:"<< runTime <<"\n"<<endl;
        MiningProcess(root, lnkhdr, basePattern);
        ofstream result("result_WAP.data", ios::app);

        //cout<<"Here is the result......"<<endl;
        while( !basePattern.empty())
        {
                result << basePattern.top() <<"\t";
                //cout << basePattern.top() <<"\t";
                basePattern.pop();
        }
        result<<endl;
        //cout<<"\n\n";
        return;

}