maxseqtree.cpp

挖掘频繁闭序列的算法是序列挖掘算法早期比较著名的算法

#include "../Global.h"
#include "../ProjDB.h"
#include "SeqTree.h"

#if defined( _FIND_MAX_SEQS )

// Assumes itemsets have the same size.
inline bool ItemSetGreater( ItemSet * a, ItemSet * b )
{
	if( (*a).NumOfItems() > (*b).NumOfItems() )
		return true;
	else if( (*a).NumOfItems() < (*b).NumOfItems() )
		return false;

	for( int i=0; i<(*a).NumOfItems(); i++ )
	{
		if( (*a).Items[i] > (*b).Items[i] )
			return true;
		if( (*a).Items[i] < (*b).Items[i] )
			return false;
	}
	return false;
}

inline bool SeqGreater( Sequence * a, Sequence * b )
{
	ElementVector::iterator aItrtr;
	ElementVector::iterator bItrtr;

	if( (*a).Sup > (*b).Sup )
		return true;
	else if( (*a).Sup < (*b).Sup )
		return false;
	else if( (*a).Elements.size() > (*b).Elements.size() )
		return true;
	else if( (*a).Elements.size() < (*b).Elements.size() )
		return false;

	bItrtr = (*b).Elements.begin();
	for( aItrtr = (*a).Elements.begin(); aItrtr != (*a).Elements.end(); aItrtr++)
	{
		if( ItemSetGreater( *aItrtr, *bItrtr ) )
			return true;
		if( ItemSetGreater( *bItrtr, *aItrtr ) )
			return false;
		bItrtr++;
	}
	return false;
}

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

ItemSet::ItemSet( int NumItems, int * Itms )
{
	int i;

	Count = NumItems;
	Items = new int[Count];

	if( Itms )
		for( i=0; i<Count; i++ )
		{
			Items[i]=Itms[i];
		}

}

ItemSet::ItemSet( ItemSet * anItemSet )
{
	int i;

	Count = (*anItemSet).NumOfItems();
	Items = new int[Count];

	if( (*anItemSet).Items )
		for( i=0; i<Count; i++ )
		{
			Items[i]=(*anItemSet).Items[i];
		}
}

inline bool ItemSet::IsSubsetOf( ItemSet * anItemSet )
{
	int j;
	int MyCnt;
	int OtherCnt;

	MyCnt = NumOfItems();
	OtherCnt = (*anItemSet).NumOfItems();

	if( MyCnt > OtherCnt )
		return false;

	j = 0;
	for( int i=0; i<MyCnt; i++ )
	{
		while( Items[i] != (*anItemSet).Items[j] )
		{
			j++;
			if( OtherCnt-j < MyCnt-i ) 
				return false;
		}
	}

	return true;
}

inline bool ItemSet::IsLessThan( ItemSet * anItemSet )
{
	int MyCnt;
	int OtherCnt;

	MyCnt = NumOfItems();
	OtherCnt = (*anItemSet).NumOfItems();

	if( MyCnt < OtherCnt )
		return true;

	if( MyCnt > OtherCnt )
		return false;

	// MyCnt == OtherCnt
	for( int i=0; i<MyCnt; i++ )
	{
		if( Items[i] < (*anItemSet).Items[i] )
			return true;
		if( Items[i] > (*anItemSet).Items[i] )
			return false;
	}

	return true;
}

inline int ItemSet::Compare( ItemSet * anItemSet )
{
	int MyCnt;
	int OtherCnt;

	MyCnt = NumOfItems();
	OtherCnt = (*anItemSet).NumOfItems();

	if( MyCnt < OtherCnt )
		return -1;

	if( MyCnt > OtherCnt )
		return +1;

	// MyCnt == OtherCnt
	for( int i=0; i<MyCnt; i++ )
	{
		if( Items[i] < (*anItemSet).Items[i] )
			return -1;
		if( Items[i] > (*anItemSet).Items[i] )
			return +1;
	}

	return 0;
}

void ItemSet::Print1( FILE *aFile )
{
	int i;

	fprintf( aFile, " (" );
	for( i=0; i<Count; i++ )
	{
		fprintf( aFile, " %d ", Items[i] );
	}
	fprintf( aFile, ") " );

}

void ItemSet::Print( FILE *aFile )
{
	int i;

	fprintf( aFile, " (" ); 
	for( i=0; i<Count; i++ ) 
	{
		fprintf( aFile, " %d ", Items[i] );
	}
	fprintf( aFile, ") " );

}

void ItemSet::Add ( int Item )
{
	int i;
	int * tmp;

	tmp = new int[Count+1];


	for( i=0; i<Count; i++ )
	{
		tmp[i] = Items[i];
	}
	tmp[Count] = Item;
	delete[] Items;
	Items = tmp;

	Count++;
}

ItemSet::~ItemSet()
{
	delete[] Items;
}

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

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

Sequence::Sequence()
{
	Sup = 0;
}

Sequence::Sequence( Sequence * aSeq )
{
  ElementVector::iterator Itrtr;

	Sup = (*aSeq).Sup;

	for( Itrtr = (*aSeq).Elements.begin(); Itrtr != (*aSeq).Elements.end(); Itrtr++)
		Add( new ItemSet( (*Itrtr) ) );

}

Sequence::Sequence( int * Ptr, int Support )
{
	ItemSet * anItemSet;
	int Start;

	Sup = Support;

	Start = 0;

  int * dataset = Ptr;
	int * StartPtr = Ptr;

	int i = 0;

  for (; *dataset!=-2; dataset++)
	{
		if( *dataset == -1 )
		{
			anItemSet = new ItemSet( i-Start, StartPtr );
			StartPtr = dataset + 1;
			Start = i+1;
			Add( anItemSet );
		}
		i++;
	}
	//Print();
	//printf( "\n" );
}

Sequence::Sequence( int * Pat, int PatLen, int Support )
{
	ItemSet * anItemSet;
	int Start;

	Sup = Support;

	Start = 0;

	if( PatLen > 1 )
	{
		for( int i=0; i<PatLen; i++)
		{
			if( *(Pat + i) == -1 )
			{
				anItemSet = new ItemSet( i-Start, Pat+Start );
				Start = i+1;
				Add( anItemSet );
			}
		}
		anItemSet = new ItemSet( i-Start, Pat+Start );
		Add( anItemSet );
	} else {
		int tmp[1];
		tmp[0] = *Pat;
		anItemSet = new ItemSet( 1, tmp );
		Add( anItemSet );
	}
}

Sequence::Sequence( const struct PROJ_DB *proj_db, int Support )
{
	ItemSet * anItemSet;
	int Start;

	Sup = Support;

	Start = 0;

	if( proj_db[0].m_nPatLen > 1 )
	{
		for( int i=0; i<proj_db[0].m_nPatLen; i++)
		{
			if( proj_db[0].m_pnPat[i] == -1 )
			{
				anItemSet = new ItemSet( i-Start, &proj_db[0].m_pnPat[Start] );
				Start = i+1;
				Add( anItemSet );
			}
		}
		anItemSet = new ItemSet( i-Start, &proj_db[0].m_pnPat[Start] );
		Add( anItemSet );
	} else {
		int tmp[1];
		tmp[0] = int( proj_db[0].m_pnPat );
		anItemSet = new ItemSet( 1, tmp );
		Add( anItemSet );
	}

//	Print();
//	printf( "\n" );
}

Sequence::Sequence( const struct PROJ_DB *proj_db, int * aSeqPtr ) //: Sequence( proj_db, 0 )
{
#if defined( _PERFORM_COMMON_PREFIX_CHECKING )
	int * aPtr;
	int i;
	SeqWrap * aSeq;

	if( (*proj_db).m_nPatLen > 1 )
	{
		for( int j=0; j<(*proj_db).m_nPatLen; j++ )
			buf_idx[j] = (*proj_db).m_pnPat[j];
	} else
		buf_idx[0] = int( (*proj_db).m_pnPat );

	i = (*proj_db).m_nPatLen;
	aPtr = aSeqPtr;

	aSeq = new SeqWrap( aSeqPtr );

	aPtr = (*aSeq).GetFirst();

	while( *aPtr != -2 )
	{
		buf_idx[i++] = *aPtr;
		aPtr = (*aSeq).GetNext();
	}

	delete aSeq;

	int PatLen = i - 1;
	int * Pat = buf_idx;

/////////////////
	ItemSet * anItemSet;
	int Start;

	Sup = 0;

	Start = 0;

	if( PatLen > 1 )
	{
		for( int i=0; i<PatLen; i++)
		{
			if( *(Pat + i) == -1 )
			{
				anItemSet = new ItemSet( i-Start, Pat+Start );
				Start = i+1;
				Add( anItemSet );
			}
		}
		anItemSet = new ItemSet( i-Start, Pat+Start );
		Add( anItemSet );
	} else {
		int tmp[1];
		tmp[0] = *Pat;
		anItemSet = new ItemSet( 1, tmp );
		Add( anItemSet );
	}

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


#endif // defined( _PERFORM_COMMON_PREFIX_CHECKING )
}


#if !defined( _USE_MAX_TREE )
// Returns true if this sequence is the Max subset of aSeq.
bool Sequence::IsMaxSubsetOf( Sequence * aSeq )
{
  ElementVector::iterator aSeqPtr;
  ElementVector::iterator thisPtr;

	int aSeqLen = (*aSeq).Elements.size();
	int thisLen = Elements.size();

	if( Elements.size() == 0 )
		return true;

	thisPtr = Elements.begin();
	aSeqPtr = (*aSeq).Elements.begin();

	if( aSeqLen >= thisLen && aSeqLen > 0 )
	{
		while( aSeqPtr != (*aSeq).Elements.end() )
		{
			if( (*(*thisPtr)).IsSubsetOf( (*aSeqPtr) ) )
				thisPtr++;
			if( thisPtr == Elements.end() )
				return true;

			aSeqPtr++;
		}
	}

	return false;

}

#endif // !defined( _USE_MAX_TREE )

void Sequence::Add( struct PROJ_SEQ * PrjSeq )
{
	ItemSet * anItemSet;
	int * Start;
	int * intPtr;

	MoveLast();
	anItemSet = Current();

	if( (*PrjSeq).m_nProjCount > 1 )
		intPtr = (*PrjSeq).m_ppSeq[0];
	else
		intPtr = (int *)(*PrjSeq).m_ppSeq;

	// Should be improvemnet. 123
	while( *intPtr != -1 && *intPtr != -2 )
	{
		(*anItemSet).Add( *intPtr );
		intPtr ++;
	}

	while( *intPtr != -2 )
	{
		Start = intPtr;
		while( *intPtr != -1 )
		{
 
			intPtr ++;
		}
		if( Start != intPtr )
		{
			anItemSet = new ItemSet( intPtr-Start, Start );
			Add( anItemSet );
		}
		intPtr ++;
	}
}


void Sequence::Print( FILE *aFile )
{
  ElementVector::iterator Itrtr;

	fprintf( aFile, " <" );

	for( Itrtr = Elements.begin(); Itrtr != Elements.end(); Itrtr++)
		(*(*Itrtr)).Print( aFile );

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

}

Sequence::~Sequence()
{
  ElementVector::iterator Itrtr;

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

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

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

//************************
//************************
#if defined( _USE_MAX_TREE )
//************************
//************************
SeqTree::SeqTree( int ItemsCount )
{
	Root = new TreeNode();
	NumOfItems = ItemsCount;
	Header = new NodeVector[NumOfItems+1];
	//Header = new NodeList[NumOfItems+1];

	NumOfAdds = 0;
	NumOfDels = 0;
	NumOfAddIfClosed = 0;
	NumIsMaxSubsetOf = 0;

}

bool TreeNodeLevelLess( TreeNode * a, TreeNode * b )
{
	return (*a).Level > (*b).Level;
}

int TreeNodeLevelCompare( TreeNode ** a, TreeNode ** b )
{
	if( (*(*a)).Level < (*(*b)).Level )
		return 1;
	else if( (*(*a)).Level > (*(*b)).Level )
		return -1;
	else   
		return 0;
	//return (*(*(*a)).Item).Compare( (*(*b)).Item );
}

void SeqTree::RemoveFromHeaderList( TreeNode * aNode )
{
	ItemSet * anItemSet;
	int anItem;
	TreeNode ** Res;
  NodeVector::iterator Itrtr;

	anItemSet = (*aNode).Item;
	// Delete the links from the header table
	for( int i=0; i<(*anItemSet).NumOfItems(); i++ )
	{
		anItem = (*anItemSet).Items[i];

		Res = (TreeNode **) bsearch( &aNode, Header[anItem].begin(), Header[anItem].size(), sizeof( TreeNode *), (int (*)(const void*, const void*))TreeNodeLevelCompare );

		if( !Res ) continue;

		Itrtr = Res;
		
		while( (*(*Itrtr)).Level == (*aNode).Level && Itrtr != Header[anItem].begin() ) 
			Itrtr--;
		
		while( (*(*Itrtr)).Level >= (*aNode).Level && Itrtr != Header[anItem].end() ) 
		{
			if( (*Itrtr) == aNode )
				Itrtr = Header[anItem].erase( Itrtr );
			else
				 Itrtr++;
		}
	}
	
}

void SeqTree::DeleteSequence( TreeNode * aNode )
{
	TreeNode * Parent;


	if( (*aNode).NumOfChildren() == 0 && (*aNode).Parent )
	{
		RemoveFromHeaderList( aNode );

		Parent = (*aNode).Parent;

		//if( (*Parent).NumOfChildren() > 1 )
			(*Parent).DelChild( aNode );

		//DeleteSequence( (*aNode).Parent );
		DeleteSequence( Parent );

		delete aNode;
	}

}

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

	(*aSeq).MoveLast();
	anItemSet = (*aSeq).Current();
	CurNode = aNode;
	NumOfRemElmnts = (*aSeq).NumOfElements();

	NumIsMaxSubsetOf++;

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

		} else {
			CurNode = (*CurNode).Parent;
			if( (*CurNode).Level < NumOfRemElmnts )
				return false;
		}
	}
}

// Returns the item in the anItemSet, with shortest header list.
int SeqTree::LeastFreqInHeader( ItemSet * anItemSet )
{
	int anItem;
	int Res = -1;
	int Min = 10000000;
	int HeaderSize;

	for( int i=0; i<(*anItemSet).NumOfItems(); i++ )
	{
		anItem = (*anItemSet).Items[i];
		HeaderSize = Header[anItem].size();
		if( HeaderSize < Min )
		{
			Min = HeaderSize;
			Res = anItem;
		}
		if( Min==0 ) break;
	}

	return Res;
}