closedseqtree.cpp

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

#include <assert.h>
#include "../Global.h"
#include "../ProjDB.h"

#if !defined( _FIND_MAX_SEQS ) && !defined( _FIND_FREQUENT_SEQS )

//#include "SequenceList.h"

void RTATest( const struct PROJ_DB * pDB );

/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////

#if defined( _USE_OUTPUT_BUFFER )

void EmptyBuffer( SequenceList * aList, Sequence * aSeq )
{
	Sequence * aBuf;
	Sequence * aParent;
	int tmpSup = 0;

	if( n_max_mem < n_total_mem )
		n_max_mem = n_total_mem;

	aBuf = aSeq;
	while( aBuf != NULL )
	{
		aParent = (*aBuf).Parent;
		(*aBuf).ReferenceCount--;
		if( (*aBuf).ReferenceCount <= 0 )
		{
			if( (*aBuf).Support > tmpSup )
			{
				tmpSup = (*aBuf).Support;
				(*aList).AddIfClosedSeq( aBuf );
			} else {
				delete aBuf;
			}

		} else
			break;
		aBuf = aParent;
	}
	
	// Ignor parent sequences that have the same support, when traversing through their other children.
	while( aBuf != NULL && (*aBuf).Support <= tmpSup )
	{
		(*aBuf).Support = -1;
		aBuf = (*aBuf).Parent;
	}

}

#endif


/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////


void main1( int argc, char** argv )
{
	printf( "This is SequenceList running!!!\n" );


}



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


Sequence::Sequence()
{
	StartPtr = NULL;
	Support = 0;
	Len = 0;
#if defined( _USE_OUTPUT_BUFFER )
	Parent = NULL;
	ReferenceCount = 0;
#endif
}

// No last -1, and -2 are presented.
Sequence::Sequence( int * Ptr, int Len, int Sup )
{
	int tmp;
	Support = Sup;
	(*this).Len = Len;
#if defined( _USE_OUTPUT_BUFFER )
	Parent = NULL;
	ReferenceCount = 0;
#endif

	tmp = (*this).Len * sizeof( int );
	StartPtr = (int*) memalloc( tmp );
	n_total_mem += ( tmp  + sizeof( *this ) );
	memcpy( StartPtr, Ptr, tmp );
}

inline bool Sequence::EndOfSequence( int * aPtr )
{
	return (aPtr-StartPtr >= Len);
}

inline bool Sequence::EndOfItemSet( int * aPtr )
{
	return (*aPtr==-1) || (aPtr-StartPtr >= Len);
}

inline int Sequence::NumOfItemSets()
{
	int * ItemPtr;
	int Result = 0;

	if( Len>0 )
		Result = 1;

	for( ItemPtr = StartPtr; !EndOfSequence( ItemPtr ); ItemPtr++ )
	{
		if( *ItemPtr == -1 )
			Result++;
	}
	return Result;
}

// Returns the address of the next itemset in aSeq, if itemset pointed to by ThisStart
// is the subset of the itemset pointed to by SeqStart.
inline int * Sequence::IsItemSetSubsetOf( int * ThisStart, int * SeqStart, Sequence * aSeq )
{
	int * aSeqPtr = SeqStart;
	int * thisPtr = ThisStart;

	while( !(*aSeq).EndOfSequence(aSeqPtr) )
	{
		if( *aSeqPtr == *thisPtr )
		{
			thisPtr++;
			if( EndOfItemSet(thisPtr) )
			{
				while( !(*aSeq).EndOfItemSet(aSeqPtr) )
					aSeqPtr++;
				return ++aSeqPtr;
			}
		}

		aSeqPtr++;
		if( (*aSeq).EndOfItemSet(aSeqPtr) )
			thisPtr = ThisStart;
	}
	return NULL;
}

// Returns true if this sequence is the closed subset of aSeq.
bool Sequence::IsClosedSubsetOf( Sequence * aSeq )
{
	int * aSeqPtr = (*aSeq).StartPtr;
	int * thisPtr = StartPtr;

	if( Len == 0 )
		return true;

	if( (*aSeq).Len >= Len && (*aSeq).Len > 0 && (*aSeq).Support >= Support )
	{
		while( !(*aSeq).EndOfSequence(aSeqPtr) )
		{
			aSeqPtr = IsItemSetSubsetOf( thisPtr, aSeqPtr, aSeq );

			if( aSeqPtr == NULL )
				return false;
			else {
				while( !EndOfItemSet(thisPtr) )
					thisPtr++;
				if( EndOfSequence(++thisPtr) )
					return true;
			}
		}

	}

	return false;
}

void Sequence::Print( FILE *aFile )
{
	int * TmpPtr = NULL;

	fprintf( aFile, " <" );


	TmpPtr = StartPtr;

	if( TmpPtr!=NULL )
		fprintf( aFile, " (" );

	while( TmpPtr != NULL && TmpPtr-StartPtr <= Len )
	{
		if( TmpPtr-StartPtr == Len )
			fprintf( aFile, ") " );
		else if( *TmpPtr == -1 )
		{
				fprintf( aFile, ")  (" );
		} else {
			fprintf( aFile, " %d ", *TmpPtr );
		}

		TmpPtr++;

	}

	fprintf( aFile, "> " );

	fprintf( aFile, "  Support = %d\n", Support );
}

Sequence::~Sequence()
{
	int tmp;

	tmp = (*this).Len * sizeof( int );
	n_total_mem -= ( tmp  + sizeof( *this ) );
	freemem( (void**) &StartPtr );
}

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

//************************
//************************
#define _CONSIDER_LEN

inline bool SeqGreater( Sequence * a, Sequence * b )
{
#if defined( _CONSIDER_LEN )
	if( (*a).Support > (*b).Support )
		return true;
	else if( (*a).Support < (*b).Support )
		return false;
	else if( (*a).Len > (*b).Len )
		return true;
	else if( (*a).Len < (*b).Len )
		return false;

	for( int i=0; i<(*a).Len; i++ )
	{
		if( *((*a).StartPtr+i) > *((*b).StartPtr+i) )
			return true;
		if( *((*a).StartPtr+i) < *((*b).StartPtr+i) )
			return false;
	}
	return false;
#else
	return (*a).Support > (*b).Support;
#endif
}

inline bool SeqGreaterEqual( Sequence * a, Sequence * b )
{
#if defined( _CONSIDER_LEN )
	if( (*a).Support > (*b).Support )
		return true;
	else if( (*a).Support < (*b).Support )
		return false;
	else
		return (*a).Len >= (*b).Len;
#else
	return (*a).Support >= (*b).Support;
#endif
}

inline bool SeqEqual( Sequence * a, Sequence * b )
{
#if defined( _CONSIDER_LEN )
	return ( (*a).Support == (*b).Support ) && ( (*a).Len == (*b).Len );
#else
	return (*a).Support == (*b).Support;
#endif
}

#if _NEW_SEQUENCE_LIST > 0 && _NEW_SEQUENCE_LIST < 20
inline bool LenGreater( Sequence * a, Sequence * b )
{
	if( (*a).Len > (*b).Len )
		return true;
	else if( (*a).Len < (*b).Len )
		return false;

	for( int i=0; i<(*a).Len; i++ )
	{
		if( *((*a).StartPtr+i) > *((*b).StartPtr+i) )
			return true;
		if( *((*a).StartPtr+i) < *((*b).StartPtr+i) )
			return false;
	}
	return false;
}
#endif // _NEW_SEQUENCE_LIST > 0 && _NEW_SEQUENCE_LIST < 20


#if defined( _NEW_SEQUENCE_LIST )

#if _NEW_SEQUENCE_LIST < 20

SequenceList::SequenceList()
{
	NumOfAdds = 0;
	NumOfDels = 0;
	NumOfAddIfClosed = 0;
	NumIsClosedSubsetOf = 0;
}


inline void SequenceList::AddSeq( Sequence * aSeq )
{
	NumOfAdds++;

#if _NEW_SEQUENCE_LIST > 0
	SeqMap::iterator Itrtr;
	SeqList * tmpSeqList;

	Itrtr = List.find( (*aSeq).Support );
	if( Itrtr != List.end() )
	{
		tmpSeqList = (*Itrtr).second;
	} else {
		tmpSeqList = new SeqList();
		List.insert( SeqMap::value_type( (*aSeq).Support, tmpSeqList ) );
	}
	(*tmpSeqList).push_back( aSeq );
	// To keep the List vector sorted.
	inplace_merge( (*tmpSeqList).begin(), (*tmpSeqList).end()-1, (*tmpSeqList).end(), LenGreater );
#else //_NEW_SEQUENCE_LIST > 0
	List.push_back( aSeq );
	// To keep the List vector sorted.
	inplace_merge( List.begin(), List.end()-1, List.end(), SeqGreater );
#endif //_NEW_SEQUENCE_LIST > 0

}

inline SeqList::iterator SequenceList::Del( SeqList::iterator anItr )
{
	NumOfDels++;
#if _NEW_SEQUENCE_LIST > 0
#else //_NEW_SEQUENCE_LIST > 0
	return List.erase( anItr );
#endif //_NEW_SEQUENCE_LIST > 0
}

// 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 closed subset of aSeq
// will be deleted from the list.
// Returns true if aSeq is added.
bool SequenceList::AddIfClosedSeq( Sequence * aSeq )
{
	NumOfAddIfClosed++;

#if _NEW_SEQUENCE_LIST > 0
	SeqMap::iterator Itrtr;
	SeqList::iterator ListItrtr;
	SeqList * aList;

	for( Itrtr = List.begin(); Itrtr != List.end() && (*Itrtr).first>=(*aSeq).Support; Itrtr++ )
	{
		aList = (*Itrtr).second;
		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end() && (*(*ListItrtr)).Len>=(*aSeq).Len; )
		{
			NumIsClosedSubsetOf++;
			if( (*aSeq).IsClosedSubsetOf( (*ListItrtr) ) )
				return false;
			if( (*aSeq).Support == (*Itrtr).first && (*(*ListItrtr)).Len == (*aSeq).Len )
			{
				NumIsClosedSubsetOf++;
				if( (*(*ListItrtr)).IsClosedSubsetOf( aSeq ) )
				{
					delete (*ListItrtr);

					NumOfDels++;
					
					ListItrtr = (*aList).erase( ListItrtr );
				} else
					ListItrtr++;
			} else
				ListItrtr++;
		}
	}

	// Go to the list with equal support with aSeq.
	if( Itrtr != List.begin() ) 
	{
		Itrtr--; 
		if( (*(Itrtr)).first != (*aSeq).Support )
			Itrtr++; 
	}

	while( Itrtr != List.end() ) 
	{
		aList = (*Itrtr).second;
		for( ListItrtr = (*aList).end()-1; ListItrtr >= (*aList).begin() && (*(*ListItrtr)).Len<=(*aSeq).Len; )
		{
			NumIsClosedSubsetOf++;
			if( (*(*ListItrtr)).IsClosedSubsetOf( aSeq ) )
			{
				delete (*ListItrtr);
				NumOfDels++;
					
				ListItrtr = (*aList).erase( ListItrtr ) - 1;
			} else
				ListItrtr--;
		}
		Itrtr++;
	}

	AddSeq( aSeq );
	return true;
#else //_NEW_SEQUENCE_LIST > 0
	SeqList::iterator Itrtr;

	Itrtr = List.begin();

	while( Itrtr != List.end() && SeqGreaterEqual( (*Itrtr), aSeq ) ) 
	{
		NumIsClosedSubsetOf++;
		if( (*aSeq).IsClosedSubsetOf( (*Itrtr) ) )
			return false;

		if( SeqEqual( aSeq, (*Itrtr) ) )
		{
			NumIsClosedSubsetOf++;
			if( (*(*Itrtr)).IsClosedSubsetOf( aSeq ) )
			{
				delete (*Itrtr);

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

	while( Itrtr != List.end() ) 
	{
		NumIsClosedSubsetOf++;
		if( (*(*Itrtr)).IsClosedSubsetOf( aSeq ) )
		{
			delete (*Itrtr);

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

	AddSeq( aSeq );
	return true;
#endif //_NEW_SEQUENCE_LIST > 0
}

void SequenceList::Print( FILE *aFile )
{
	int ListSize = 0;
	fprintf( aFile, "\n" );
#if _NEW_SEQUENCE_LIST > 0
	SeqMap::iterator Itrtr;
	SeqList::iterator ListItrtr;
	SeqList * aList;

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
	{
		aList = (*Itrtr).second;
		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end(); ListItrtr++)
		{
			(*(*ListItrtr)).Print( aFile );
			ListSize++;
		}
	}
#else //_NEW_SEQUENCE_LIST > 0
	SeqList::iterator Itrtr;

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

#endif //_NEW_SEQUENCE_LIST > 0
	fprintf( aFile, "\n" );
	fprintf( aFile, "# of elements added %d\n", NumOfAdds );
	fprintf( aFile, "# of elements deleteded %d\n", NumOfDels );
	fprintf( aFile, "# of times AddIfClosedSeq called %d\n", NumOfAddIfClosed );
	fprintf( aFile, "# of times IsClosedSubsetOf called %d\n", NumIsClosedSubsetOf );
	fprintf( aFile, "# of elements in the list %d\n", ListSize );
}

SequenceList::~SequenceList()
{
#if _NEW_SEQUENCE_LIST > 0
	SeqMap::iterator Itrtr;
	SeqList::iterator ListItrtr;
	SeqList * aList;

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
	{
		aList = (*Itrtr).second;
		for( ListItrtr = (*aList).begin(); ListItrtr != (*aList).end(); ListItrtr++)
		{
			delete (*ListItrtr);
		}
		delete aList;
	}
#else //_NEW_SEQUENCE_LIST > 0
	SeqList::iterator Itrtr;

	for( Itrtr = List.begin(); Itrtr != List.end(); Itrtr++)
		delete (*Itrtr);
#endif //_NEW_SEQUENCE_LIST > 0
}

//************************
//************************
#else // _NEW_SEQUENCE_LIST < 20
//************************
//************************

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

bool TreeNodeLess( TreeNode * a, TreeNode * b )
{
	if( (*a).ItemIsIntra == (*b).ItemIsIntra )
		return (*a).Item < (*b).Item; 
	else if( (*a).ItemIsIntra && !(*b).ItemIsIntra )
		return true;
	else
		return false;