plwap.cpp

对WAP树进行编码,从而可提高算法的效率,可以作为参考进一步改进

	{
		 
		ins >> cid;
         ins >> number;
         seqNumber++;

         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 ++;
        		else
	        			seq.insert( sequence::value_type(event,1));

		    }
        }
	}

	// next is going to filter out the event that does not meet the minimum support
        frequency = (int)(minSupp* seqNumber);

        sequence::iterator i, bi;

		i = seq.begin();
        while( i!=seq.end())
        {
            bi = i;
			if( i != seq.end())
			{
                 bi++;
			}

            if (i->second < frequency)
            {
                seq.erase(i);
                i=bi;
            }
			else
				i++;
        }
        //cout<<"Finish scanning the database: " <<endl;

// Next is build the PLWAP tree

        node *Tranversal, *newNode, *Parent;

        root = new node;
        root->event = -1;
        root->occur = seqNumber;
        root->CountSon = 0;
        root->pcLength = 0;
        root->parent = NULL;
        root->lSon = NULL;
        root->rSibling = NULL;
        root->nextLink = NULL;
        root->pcLength = 0;

        ifstream inFile ( sourceFile, ios::in);

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

		//cout <<"Begin to build tree " << endl;

		while (inFile && !inFile.eof())
		{
			inFile >> cid;
			inFile >> number;

			Tranversal = root;

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

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

                        if( Tranversal->lSon == NULL)						// inesrt first child of root
                        {
                                newNode = new node;
                                newNode->event = event;
                                newNode->occur = 1;
                                newNode->lSon = NULL;
                                newNode->rSibling = NULL;
								newNode->nextLink = NULL;
                                newNode->CountSon = 0;
                                Parent->CountSon ++;
                                newNode->parent = Parent;
                                newNode->pcLength = Tranversal->pcLength + 1;
                                newNode->pcCode = makeCode(Tranversal->pcLength,Tranversal->pcCode,true);
                                Tranversal->lSon = newNode;
                                Tranversal = newNode;
                        }
                        else
                        {						
                                Tranversal = Tranversal->lSon;
                                if ( Tranversal->event == event)								// the node is found
                                {
                                        (Tranversal->parent)->CountSon++;
                                        Tranversal->occur++;
                                }
                                else
                                {
                                        bool find= false;
                                        while(Tranversal->rSibling != NULL && !find )										//find the event in its sibling
                                        {
                                                Tranversal = Tranversal->rSibling;
                                                if ( Tranversal->event == event)
                                                {
                                                        Tranversal->occur ++;
                                                        (Tranversal->parent)->CountSon++;
                                                        find = true;
                                                }
                                        }
                                        if (!find)										//insert a new node
                                        {
                                                newNode = new node;
                                                newNode->event = event;
                                                newNode->occur = 1;
                                                newNode->lSon = NULL;
                                                newNode->rSibling = NULL;
												newNode->nextLink = NULL;
												newNode->CountSon = 0;
                                                Parent->CountSon ++;
                                                newNode->parent = Parent;
                                                newNode->pcLength = Tranversal->pcLength + 1;
                                                newNode->pcCode = makeCode(Tranversal->pcLength,Tranversal->pcCode, false);
                                                Tranversal->rSibling = newNode;
                                                Tranversal = newNode;
                                        }
                                }
                        }
				}
			}
		}

		//next tranversing all tree to build the Pre-order linkage
        linkheader *newLinkHeader;
        for (  i = seq.begin(); i!=seq.end(); i++)			//form a header table
        {
                newLinkHeader = new linkheader;
                newLinkHeader->link = NULL;
                newLinkHeader->lastLink = NULL;
                newLinkHeader->event= i->first;
                newLinkHeader->occur= i->second;
                lnkhdr.push_back(*newLinkHeader);
                free(newLinkHeader);
        }
        //cout<<"End of building tree and begin to build linkage..."<<endl;
        BuildLinkage(root->lSon);
        //cout<<"End of building linkage...\n\n";

        //cout<<"Print the WAP tree"<<endl;
//        printtree(root);
        //cout<<"\nEnd of printing WAP tree and begin printing linkage"<<endl;
//        printLinkage(lnkhdr);

        return;
}

void BuildLinkage(node *start)
{
/*
BuildLinkage is the fundtion to link the event with same label together in the tree.
It follows the pre-order style. 
Called in paremeter: the current node to be linked.
*/
        if (start !=NULL)
        {
                list<linkheader>::iterator lnkBrow = lnkhdr.begin();
                while (lnkBrow->event != start->event && lnkBrow != lnkhdr.end())
                        lnkBrow++;

                node *lastLinkage;
                lastLinkage = lnkBrow->lastLink;
                if (lastLinkage == NULL )
                        lnkBrow->link = start;
                else
                        lastLinkage->nextLink = start;
                lnkBrow->lastLink = start;

                BuildLinkage(start->lSon);
                BuildLinkage(start->rSibling);
        }
        else return;
}


positionCode * makeCode(int length, positionCode *pCode, bool addOne)
{
/*
makeCode is the function to genearte a position code for a node
Call in Parameters:
	(1) length: is the length of position code
	(2) pCode: is the position code of its parent or its nearest left 
	sibling.
	(3) addOne: is a boolean to indicate the pCode is the position code of 
	its parent or its nearest left sibling. If addOne is true, 
	then the  pCode is the position code of its parent, otherwise 
	it is the position code of its nearest left sibling.
Return value:
	The pointer of the new position code
*/
		positionCode *start, *browser, *newPC;
        int leftCount = length % 32;
        int linkCount = (int)(length / 32);

        if ( linkCount == 0 )
        {
                start = new positionCode;
                start->next = NULL;
                if (length == 0)
                        start->code = 1 << 31;
                else
                        if (addOne)
                                start->code = pCode->code | (1<<(31-leftCount));
                        else
                                start->code = pCode->code ;
                return start;
        }
        else
        {
                newPC = new positionCode;
                newPC->code = pCode->code;
                pCode = pCode ->next;
                start = newPC;
                browser = start;

                for(int i = 1; i < linkCount; i++)
                {
                        newPC = new positionCode;
                        newPC->code = pCode->code;
                        browser-> next = newPC;
                        browser = newPC;
                        pCode = pCode->next;
                }

                if (leftCount == 0)
                {
                        newPC = new positionCode;
                        if (addOne)
                                newPC->code = 1 << 31;
                        else
                                newPC->code = 0 << 31;
                        newPC->next = NULL;
                        browser->next = newPC;
                }
                else
                {
                        newPC = new positionCode;

                        if (addOne)
                                newPC->code = pCode->code | (1<<(31-leftCount));
                        else
                                newPC->code = pCode->code;

                        newPC ->next = NULL;
                        browser->next = newPC;
                }
        }

        return start;
}


int checkPosition(positionCode *FirstNode, int aLength, positionCode *SecondNode, int dLength)
{
/*
checkPosition function 
Call in parameters: 
	(1) the FirstNode's position code; 
	(2) the length of FirstNode's positon code;
	(3) the SecondNode's position code; 
	(4) the length of SecondNode's positon code.
Return Values: one of the values list below
	(1) 0: FirstNode is the ancestor of SecondNode
	(2) 1: FirstNode is in the left-tree of SecondNode
	(3) 2: FirstNode is in the right-tree of SecondNode
	(4) 3: FirstNode is the descendant of SecondNode

*/

        if (aLength == 1 )	// The length of FirstNode is 1, which means
                return 0;	
			// the FirstNode is root of whole tree, every node
			// is desendant of it.

        int length = min(aLength,dLength);  
			// determine which length of position code is bigger
        int linkCount = (int)(length / 32);
        int leftCount = length % 32;

        for( int i = 0; i < linkCount; i++)
                if ( FirstNode->code > SecondNode->code)
                        return 1;
                else
                        if ( FirstNode->code < SecondNode->code)
                                return 2;
                        else
                        {
                                FirstNode = FirstNode->next;
                                SecondNode = SecondNode->next;
                        };


        unsigned int aCode, dCode;
        if ( aLength <= dLength )
        {
                if (leftCount == 0)
                        return 0;

                aCode = FirstNode -> code >> ( 32 - leftCount );
                dCode = SecondNode -> code >> ( 32 - leftCount );
                if (aCode == dCode )
                        return 0;
                else
                        if (aCode < dCode)
                                return 2;
                        else return 1;
        }
        else
        {
                if (leftCount == 0)
                        dCode = 1;
                else
                        dCode = ( SecondNode -> code >> ( 31 - leftCount )) | 1 ;
                aCode = FirstNode -> code >> ( 31 - leftCount );


                if ( aCode == dCode )
                        return 3;
                else
                        if (aCode < dCode)
                                return 2;
                        else return 1;

        }

}