csp.cpp

CSP算法也是关联规则这方面的一个重要的算法,可根据需要下载使用

	{
	  Tranversal=root;	
	  //////Indhdr是一个串行事件的游标
	  list<linkheader>::iterator lnkBrow1 = lnkhdr.begin();
	    while (lnkBrow1 != lnkhdr.end())
		{  
			lnkBrow1->flag=0;
				lnkBrow1++;
		}
      for(int j=0;j<x;j++) 
	  {	
		  
		  event=pixel[i][j];
		 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;
//								if(lnkBrow->flag==0)
//								{
									lnkBrow->support++;
//									lnkBrow->flag=1;
//								}
                                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;
										newLinkHeader->support=1;
                                        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;
														newLinkHeader->support=1;
                                                        lnkhdr.push_back(*newLinkHeader);
                                                        free(newLinkHeader);
												   }
                                                   else
												   {
                                                        lastLinkage->nextLink = newNode;
                                                        newNode->nextLink=NULL;
                                                        lnkBrow->lastLink = newNode;
												   }
												
                                                Tranversal = newNode;
                                        }
                                }
                        }
	//////// 
/*	  if(j==(x-1) && !(i%2) && i<(y-1))
	  {
		  j=-1;
		  i++;
	  }
*/         
	  }
	  }
//	  AfxMessageBox("built finish");
  return root;
}

void Ccsp::DepthSearch(node *start)
{
	node *root=start->lSon;
	node *traverl;
	stack<node*> ptrNodeStack;
	vector<unsigned char> tmp;
//    ofstream result("result_WAP.data", ios::app);
//	bool ifexist=false;

	if(root)
	{
		if(root->occur>=minSupp)
		{
//		    num++;
//			count.push_back(root->occur);
//            tmp.Format("%uc",root->event);
//			csp_codes.push_back(tmp);
//			result<<root->occur<<"\t"<<(int)root->event<<"end"<<endl;
		    ptrNodeStack.push(root);
			while(!ptrNodeStack.empty())
			{
                 traverl=ptrNodeStack.top();
				 ptrNodeStack.pop();
				
				while(traverl->lSon && traverl->occur>=minSupp)
				{
					traverl=traverl->lSon;
					node*traverl1=traverl;
					if(traverl->occur >= minSupp)// &&
					//	(traverl->lSon==NULL||traverl->lSon->occur<minSupp)
					{
						/////////
						unsigned char index=traverl1->event;
						count[index].push_back(traverl1->occur);
//					    result<<traverl1->occur<<"\t";
					    tmp.clear();
					    while(traverl1->parent!=NULL)//&&(traverl1->event!=(unsigned char)-1))
						{
						  tmp.push_back(traverl1->event);
//						  result<<(int)traverl1->event<<"\t";
					      traverl1=traverl1->parent;
						}
				        csp_codes[index].push_back(tmp);
						
//					    result<<"end"<<endl;
					}
					ptrNodeStack.push(traverl);
				}

				////用Max_len记录每个树中最长的序列所对应的位置
/*				
				if(ifexist)
				{
					num++;
					result<<"xixixixiixixixiixiixixiixiixixiix"<<endl;
					Max_len.push_back(csp_codes.size()-1);
			     	ifexist=false;
				}
*/
			    bool flag=0;
		    	while((!flag)&&(!ptrNodeStack.empty()))
				{
				  traverl=ptrNodeStack.top();
				  ptrNodeStack.pop();
				  if(traverl->rSibling !=NULL)
				  {
					 traverl=traverl->rSibling;
					 node *p1=traverl;
					if(p1->occur>=minSupp)
					{
						unsigned char index=p1->event;
					   count[index].push_back(p1->occur);	
					   tmp.clear();
//					  result<<p1->occur<<"\t";
					  while(p1->parent!=NULL)//&&(p1->event!=(unsigned char)-1))
					  {
						  tmp.push_back(p1->event);
//					      result<<(int)p1->event<<"\t";
						  p1=p1->parent;
					  }
					  csp_codes[index].push_back(tmp);					  
//					  result<<"end"<<endl;
					  flag=1;
/*					  if(traverl->lSon)
					  {
				    	  node *t=traverl->lSon;
				    	  while(t->rSibling && t->occur < minSupp)
                              t=t->rSibling;
						  if(t->occur < minSupp)
							  Max_len.push_back(csp_codes.size()-1);
					  }
					  else
						  Max_len.push_back(csp_codes.size()-1);
*/		           
					}
					ptrNodeStack.push(traverl);
				  }
				}//while
			}

		}
	}
}

int Ccsp::Find(const vector<unsigned char> c,unsigned char index)
{
	int size;
//	unsigned char n,m;
	size=csp_codes[index].size();
	for(int i=0;i<size;i++)
	{
		if(c==csp_codes[index][i])
			return i;
	}
	return -1;
}

int Ccsp::CalculateBitSize(int value)
{
	for(int i=0;i<32;i++)
		if(value<=m_MaxCode[i])
			return i;
	return -1;
}

int Ccsp::ifPrefix(vector<unsigned char> v1,vector<unsigned char> v2)
{
	int len1=v1.size(),len2=v2.size();
	if(len1<len2)
	{
		for(int i=0;i<len1;i++)
			if(v1[i]!=v2[i]) break;
		if(i==len1)
			return 1;
		else return 0;
	}
	else if(len1>len2)
	{
		for(int i=0;i<len2;i++)
			if(v1[i]!=v2[i]) break;
		if(i==len2)
			return -1;
		else return 0;
	}

}