maxseqtree.cpp

数据挖掘中的序列模式挖掘算法clospan的C++实现

#if defined( _USE_STRING_ELEMINATION )
bool SeqTree::IsContained( const struct PROJ_DB *proj_db, int * aSeqPtr )
{
	Sequence * aSeq;
	SeqWrap * aSeqWrap;

	aSeqWrap = new SeqWrap( aSeqPtr );

	if( !(*aSeqWrap).IsEmpty() )
	{
		aSeq = new Sequence( proj_db, aSeqPtr );
		return IsContained( aSeq );
	} else {
		return false;
	}
}
#endif // defined( _USE_STRING_ELEMINATION )

bool SeqTree::IsContained( Sequence * aSeq )
{
	int anItem;
	ItemSet * LastItemSet;
  NodeVector::iterator Itrtr;
  //NodeList::iterator Itrtr;

	if( (*aSeq).NumOfElements() == 0 ) return true;

	(*aSeq).MoveLast();
	LastItemSet = (*aSeq).Current();

	// Just check for the item in the item list with shortest header list.
	anItem = LeastFreqInHeader(LastItemSet);
	if( Header[anItem].size() == 0 ) return false; 
	for( Itrtr = Header[anItem].begin(); Itrtr != Header[anItem].end(); Itrtr++)
	{
		// Header list is sorted based on the level, 
		// so stop as soon as level is less than # elements.
		if( (*(*Itrtr)).Level < (*aSeq).NumOfElements() ) // 123
			break; // 123

		if( IsSubsetOfBranch( aSeq, (*Itrtr) ) )
			return true;
	}

	return false;
}

// If aSeq is a superset of the sequence in the tree with aNode as its last element.
bool SeqTree::IsSupersetOfBranch( Sequence * aSeq, TreeNode * aNode )
{
	int NumOfRemElmnts;
	ItemSet * anItemSet;
	TreeNode * CurNode;

	NumIsMaxSubsetOf++;

	if( (*aNode).NumOfChildren() > 0 || (*aNode).Level > (*aSeq).NumOfElements() )
		return false;
						
	(*aSeq).MoveLast();
	anItemSet = (*aSeq).Current();
	CurNode = aNode;
	NumOfRemElmnts = (*aSeq).NumOfElements();

	if( (*CurNode).Level > NumOfRemElmnts )
		return false;
	
	while( true )
	{
		if( (*CurNode).Level == 0 )
			return false;
		if( (*(*CurNode).Item).IsSubsetOf( anItemSet ) )
		{
			CurNode = (*CurNode).Parent;
			(*aSeq).MovePrev();
			anItemSet = (*aSeq).Current();
			NumOfRemElmnts--;
			if( (*CurNode).Level == 0 )
				return true;

		} else {
			(*aSeq).MovePrev();
			anItemSet = (*aSeq).Current();
			NumOfRemElmnts--;
			if( (*CurNode).Level > NumOfRemElmnts )
				return false;
		}
	}
}

void SeqTree::PrintHeaderList( int anItem )
{
	printf(" ======= Size of the Header list for item %d =%d \n", anItem, Header[anItem].size() );
  NodeVector::iterator myIt;
  NodeVector::iterator BIt;
  NodeVector::iterator EIt;
  //NodeList::iterator myIt;
  //NodeList::iterator BIt;
  //NodeList::iterator EIt;
	BIt = Header[anItem].begin();
	EIt = Header[anItem].end();
	EIt--;
	//printf(" Head = " );
	//(*(*(*BIt)).Item).Print();
	//printf("\n End = " );
	//(*(*(*EIt)).Item).Print();
	//printf("\n" );
	for( myIt = Header[anItem].begin(); myIt != Header[anItem].end(); myIt++)
	{
		try 
		{
			(*(*(*myIt)).Item).Print();
			printf( "%d %d", (*(*myIt)).Level, (*myIt) ); 
		}
		catch(...) 
		{
			printf("*Err*" );
		}

	}
	printf("\n =================== End\n" );
}

void SeqTree::DeleteSubsets( Sequence * aSeq )
{
	int anItem;
	ItemSet * anItemSet;
  ElementVector::iterator ElementItrtr;
  NodeVector::iterator Itrtr;
  //NodeList::iterator Itrtr;
  NodeVector::iterator tmpItrtr;
  //NodeList::iterator tmpItrtr;

	// For each element, anItemSet, in aSeq.
	for( ElementItrtr = (*aSeq).Elements.begin(); ElementItrtr != (*aSeq).Elements.end(); ElementItrtr++)
	{
		anItemSet = (*ElementItrtr);

		// For each item, anItem, in anItemSet.
		for( int i=0; i<(*anItemSet).NumOfItems(); i++ )
		{
			anItem = (*anItemSet).Items[i];
			if( Header[anItem].size() > 0 )
			{
				Itrtr = Header[anItem].end() - 1;
				while( Itrtr != Header[anItem].begin() - 1 )
				{
					try 
					{
						if( (*(*Itrtr)).Level > (*aSeq).NumOfElements() ) break; //123
						
						if( IsSupersetOfBranch( aSeq, (*Itrtr) ) )
						{
							tmpItrtr = Itrtr;
							tmpItrtr--;

							NumOfDels++;
							DeleteSequence( (*Itrtr) );
							Itrtr = tmpItrtr;
						} else 
							Itrtr--;
					} catch(...)	{
						Itrtr--;
						printf( " Error in Delete Subsets in SeqTree.\n" );
					}
				}

			}
		}
	}
}


int SeqTree::AddSeq( Sequence * aSeq )
{
	TreeNode * tmp;
	TreeNode * Current;
	ItemSet * anItemSet;
	bool * Duplicated;
	int anItem;
	int CurrentLevel;

	//printf("==============>");
	//(*aSeq).Print();
	NumOfAddIfClosed++;
	// aSeq was not added.
	if( IsContained( aSeq ) ) return 1;

	DeleteSubsets( aSeq );

	Current = Root;
	(*Current).Sup = (*aSeq).Sup;

	Duplicated = (bool *)calloc( NumOfItems, sizeof(bool) );

	(*aSeq).MoveFirst();

	CurrentLevel = 1;

	while( !(*aSeq).IsLast() )
	{
		anItemSet = (*aSeq).Current();

		tmp = (*Current).FindChild( anItemSet );


		if( !tmp )
		{ // Add a new node to tree
			tmp = new TreeNode( anItemSet );
			(*tmp).Parent = Current;
			(*tmp).Level = CurrentLevel;

			(*Current).AddChild( tmp );
		}

		Current = tmp;
		(*Current).Sup = (*aSeq).Sup;

		(*aSeq).MoveNext();
		CurrentLevel++;
	}
	(*Current).Sup = (*aSeq).Sup;

	// Add the last instance of each item in the sequence to the header list.
	while( Current != Root )
	{
		anItemSet = (*Current).Item;

		for( int i=0; i<(*anItemSet).NumOfItems(); i++ )
		{
			anItem = (*anItemSet).Items[i];
			if( !Duplicated[ anItem ] )
			{
				Header[anItem].push_back( Current );
				// To keep the Header lists sorted.
				inplace_merge( Header[anItem].begin(), Header[anItem].end()-1, Header[anItem].end(), TreeNodeLevelLess ); //123
			}

			Duplicated[ anItem ] = true;
		}
		Current = (*Current).Parent;
	}

	// aSeq was added.
	NumOfAdds++;
	return 0;
}

void SeqTree::Print( FILE * aFile )
{
  NodeVector::iterator Itrtr;
  //NodeList::iterator Itrtr;

	if( Root )
		(*Root).Print( aFile );

	fprintf( aFile, "\n Header Table:\n" );

	for( int i=0; i<NumOfItems; i++ )
	{

		fprintf( aFile, "  List for %d (Len=%d) => ", i, Header[i].size() );
		for( Itrtr = Header[i].begin(); Itrtr != Header[i].end(); Itrtr++)
		{
			fprintf( aFile, "  " );
			if( (*(*Itrtr)).Item ) (*(*(*Itrtr)).Item).Print();
		}
		fprintf( aFile, " \n" );
	}
}

void SeqTree::InternalPrintRules( FILE * aFile, TreeNode * InNode, Sequence * aSeq, SeqList * SortedSeqList )
{

	TreeNode * aNode;
	TreeNode * aChild;

	if( InNode )
		aNode = InNode;
	else {
		aNode = Root;
		NumOfSeqs = 0;
	}

	if( !aSeq )
		aSeq = new Sequence();


	if( !aNode ) return;

	if( (*aNode).NumOfChildren() == 0 )
	{
		(*aSeq).Sup = (*aNode).Sup;

		
		if( SortedSeqList == NULL )
		{
			(*aSeq).Print( aFile );
		} else {
			(*SortedSeqList).push_back( new Sequence( aSeq ) );
			// To keep the List vector sorted.
			inplace_merge( (*SortedSeqList).begin(), (*SortedSeqList).end()-1, (*SortedSeqList).end(), SeqGreater );
			//(*(*(*SortedSeqList).begin())).Print();
		}
		
		NumOfSeqs++;
	}

	//fprintf( aFile, "\n Rules:\n" );

	(*aNode).MoveFirst();
	while( !(*aNode).IsLast() )
	{
		aChild = (*aNode).Current();
		//(*(*aChild).Item).Print( aFile );
		if( aChild )
		{
			(*aSeq).Add( (*aChild).Item );
			InternalPrintRules( aFile, aChild, aSeq, SortedSeqList );
		}
		(*aSeq).Del();
		(*aNode).MoveNext(); 
		//if( !(*aNode).IsLast() )
			//fprintf( aFile, " Support = %d\n", (*aNode).Sup );
	}
	if( (*aSeq).NumOfElements() == 0 )
	{
		//fprintf( aFile, " Support = %d\n", (*aNode).Sup );
		delete aSeq;
	}
}

void SeqTree::PrintRules( FILE * aFile, TreeNode * InNode, Sequence * aSeq )
{
	
	SeqList * SortedSeqList = NULL;

	#if defined( _SORT_RESULTS )
		SeqList::iterator ListItrtr;
		SortedSeqList = new SeqList;
	#endif

	InternalPrintRules( aFile, InNode, aSeq, SortedSeqList );

#if defined( _SORT_RESULTS )
	fprintf( aFile, "\n" );
	for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )
	{
		(*(*ListItrtr)).Print( aFile );
	}
	delete SortedSeqList;
#endif

	fprintf( aFile, "\n" );
	fprintf( aFile, "# of elements added %d\n", NumOfAdds );
	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );
	fprintf( aFile, "# of times AddIfMaxSeq called %d\n", NumOfAddIfClosed );
	fprintf( aFile, "# of times IsMaxSubsetOf called %d\n", NumIsMaxSubsetOf );
	fprintf( aFile, "# of elements in the list %d\n", NumOfSeqs );

}

SeqTree::~SeqTree()
{
	delete[] Header;
	delete Root;
}
//************************
//************************

//************************
//************************
TreeNode::TreeNode( ItemSet * anItemSet, int Support )
{
	Item = anItemSet;
	Sup = Support;
	Parent = NULL;
	Level = 0;
}

bool TreeNodeLess( TreeNode * a, TreeNode * b )
{
	return (*(*a).Item).IsLessThan( (*b).Item ) ;
}

void TreeNode::AddChild( TreeNode * Child ) 
{ 
	Children.push_back(Child); 
	// To keep the children vector sorted.
	inplace_merge( Children.begin(), Children.end()-1, Children.end(), TreeNodeLess );
}

int TreeNodeCompare( TreeNode ** a, TreeNode ** b )
{
	return (*(*(*a)).Item).Compare( (*(*b)).Item );
}

TreeNode * TreeNode::FindChild( ItemSet * anItem )
{
	TreeNode ** Res;
	TreeNode * tmp = new TreeNode(anItem);

	Res = (TreeNode **) bsearch( &tmp, Children.begin(), Children.size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );

	if( Res )
		return (*Res);

	return NULL;
}

void TreeNode::DelChild( TreeNode * Child )
{
	TreeNode ** Res;

	if( NumOfChildren() == 1 )
	{
		Res = Children.begin();
	} else {
		Res = (TreeNode **) bsearch( &Child, Children.begin(), Children.size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeCompare );
	}

	if( Res )
	{
		Children.erase( (Res) );
		//return (*Res);
	}

}

void TreeNode::Print( FILE * aFile )
{
  NodeVector::iterator Itrtr;

	fprintf( aFile, "  Node = " );
	if( Item ) (*Item).Print();

	fprintf( aFile, "  Level=%d ", Level );

	fprintf( aFile, " Suport = %d ) ", Sup );

	fprintf( aFile, "   Children " );

	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)
	{

		if (Itrtr != Children.end()-1 )
		{
			if( (*(*Itrtr)).Item ) (*((*(*Itrtr)).Item)).Print();
			fprintf( aFile, " ," );
		} else {
			if( (*(*Itrtr)).Item ) (*((*(*Itrtr)).Item)).Print();
		}
	}

	fprintf( aFile, "\n" );
	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)
	{
		//fprintf( aFile, "    " );
		(*(*Itrtr)).Print( aFile );
	}

	//fprintf( aFile, "\n" );
}


TreeNode::~TreeNode()
{
  NodeVector::iterator Itrtr;

	if( Item ) 
	{
		delete Item;
		Item = NULL;
	}

	for( Itrtr = Children.begin(); Itrtr != Children.end(); Itrtr++)
		delete *Itrtr;

}
//************************
//************************

//************************
//************************
#else //if defined( _USE_MAX_TREE )
//************************
//************************

SeqTree::SeqTree( int dummy )
{
	NumOfAdds = 0;
	NumOfDels = 0;
	NumOfAddIfMax = 0;
	NumIsMaxSubsetOf = 0;
}

inline void SeqTree::Add( Sequence * aSeq )
{
	List.insert( List.end(), aSeq );
	NumOfAdds++;
}

inline SeqList::iterator SeqTree::Del( SeqList::iterator anItr )
{
	NumOfDels++;
	return List.erase( anItr );
}

// Tries to add aSeq to the list if non of the list elements
// is a closed superset of aSeq.
// Sequences in the list that are Max subset of aSeq
// will be deleted from the list.
// Returns true if aSeq is added.
bool SeqTree::AddSeq( Sequence * aSeq )
{
	SeqList::iterator Itrtr;
	bool IsSuper = false;

	NumOfAddIfMax++;
	for( Itrtr = List.begin(); Itrtr != List.end(); )
	{
		if( !IsSuper )
		{
			NumIsMaxSubsetOf++;
			if( (*aSeq).IsMaxSubsetOf( (*Itrtr) ) )
				return false;
		}

		NumIsMaxSubsetOf++;
		if( (*(*Itrtr)).IsMaxSubsetOf( aSeq ) )
		{

			delete (*Itrtr) ;

			IsSuper = true;
			Itrtr = Del( Itrtr );
		} else
			Itrtr++;
	}

	Add( aSeq );
	return true;
}

bool SeqTree::IsContained( const struct PROJ_DB *proj_db, int * aSeqPtr )
{
	bool temp;
	Sequence * aSeq;

	aSeq = new Sequence( proj_db, aSeqPtr );

	temp = IsContained( aSeq );
	//(*aSeq).Print();
	//if( temp )
	//	printf( "     Is contained in the resultset.\n" );
	//else
	//	printf( "     Is NOT contained in the resultset.\n" );

	return temp;
}

bool SeqTree::IsContained( Sequence * aSeq )
{
	SeqList::iterator Itrtr;


	for( Itrtr = List.begin(); Itrtr != List.end(); )
	{
		NumIsMaxSubsetOf++;
		if( (*aSeq).IsMaxSubsetOf( (*Itrtr) ) )
			return true;
	}

	return false;
}

void SeqTree::PrintRules( FILE *aFile )
{

	SeqList::iterator Itrtr;

#if defined( _SORT_RESULTS )
  SeqList::iterator ListItrtr;
	SeqList * SortedSeqList = NULL;
	SortedSeqList = new SeqList;
#endif

	fprintf( aFile, "\n" );

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
	{
		#if defined( _SORT_RESULTS )
			(*SortedSeqList).push_back( (*Itrtr) );
			// To keep the List vector sorted.
			inplace_merge( (*SortedSeqList).begin(), (*SortedSeqList).end()-1, (*SortedSeqList).end(), SeqGreater );

		#else
			(*(*Itrtr)).Print( aFile );
		#endif
	}

#if defined( _SORT_RESULTS )
	fprintf( aFile, "\n" );
	for( ListItrtr=(*SortedSeqList).begin(); ListItrtr<(*SortedSeqList).end(); ListItrtr++ )
	{
		(*(*ListItrtr)).Print( aFile );
	}
	delete SortedSeqList;
#endif

	fprintf( aFile, "\n" );
	fprintf( aFile, "# of elements added %d\n", NumOfAdds );
	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );
	fprintf( aFile, "# of times AddIfMaxSeq called %d\n", NumOfAddIfMax );
	fprintf( aFile, "# of times IsMaxSubsetOf called %d\n", NumIsMaxSubsetOf );
	fprintf( aFile, "# of elements in the list %d\n", List.size() );

}

SeqTree::~SeqTree()
{
	SeqList::iterator Itrtr;

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
		delete *Itrtr;
}
//************************
//************************
#endif // defined( _USE_MAX_TREE )


//************************
//************************

#endif // defined( _FIND_MAX_SEQS )